class Invert {
  public static void main(String[] args) {
    for (int i = 0; i < args.length; i+=1) {
      try {
	long a = Long.decode(args[i]).longValue();
	for (long j = 1; j < a; j++) {
	  test(j, a);
	}
      } catch (Throwable ex) {
	ex.printStackTrace();
      }
    }
  }
  
  static int steps;
  static int maxsteps;

  public static void test (long a, long b) {
    steps = 0;
    try {
      long c =  invert(a, b);
      long d = ((long)a*c) % b;
      if (d != 1 || c > b) {
	System.out.println("" + a + " inverse mod " + b + " = " + c + ", check = " + d);
      }
      if (steps > maxsteps) {
	System.out.println("New maxsteps = " + steps +
			   " for inverse of " + a +
			   "(0x"+Long.toHexString(a)+"), inverse is " + c + "(0x"+Long.toHexString(c)+")");
	maxsteps = steps;
      }
      // System.out.println("" + a + " inverse mod " + b + " = " + c + ", check = " + d);
    } catch (IllegalArgumentException ex) {
      // System.out.println("" + a + " inverse mod " + b + " does not exist.");
    }
  }

	// a mod b
  public static long invert(long a, long b) {
    if (a == 1) return a;
    long q1 = b / a;
    long q2 = q1 + 1;
    long r1 = (a*q1) - b;
    long r2 = a + r1;
    return invert_helper(q1, q2, r1, r2);
  }

  public static long invert_helper(long q1, long q2, long r1, long r2) {
    // System.out.println("invert_helper(" + q1 + ", " + q2 + ", " + r1 + ", " + r2 + ")");
    // r1 is negative.
    steps++;
    if (r2 == 1) return q2;
    if (r1 == -1) return q2 + (r2-1)*q1;
    if (r1 == 0 || r2 == 0) throw new IllegalArgumentException();
    if (-r1 > r2) {
      // How many r2s make up a r1?
      long q = (-r1)/r2;
      long qa = q1 + q * q2;
      long qb = qa + q2;
      long ra = r1 + q * r2;
      long rb = ra + r2;
      return invert_helper(qa, qb, ra, rb);
    } else if (-r1 < r2) {
      // How many r1s make up a r2?
      long q = r2/(-r1);
      long qb = q2 + q * q1;
      long qa = qb + q1;
      long rb = r2 + q * r1;
      long ra = rb + r1;

      return invert_helper(qa, qb, ra, rb);
      
    } else throw new IllegalArgumentException();
  }
}