import java.math.BigInteger;
public class B_SPRP
{
public static BigInteger mulmod( BigInteger x, BigInteger y, BigInteger z)
  {
  // return ((x*y)%z);
  return (x.multiply(y)).remainder(z);
  }

public static BigInteger modexpo(BigInteger a, BigInteger b, BigInteger m)
  {
  BigInteger n = BigInteger.valueOf(1L);
/*
We find the binary representation of b while at the same time
computing successive squares of a. The variable n records the product
of the powers of a.
*/
  while ( b.compareTo(BigInteger.valueOf(0L)) > 0 )	// ( b > 0 )
    {
    if (((b.and(BigInteger.valueOf(1L))).compareTo(BigInteger.valueOf(0L))) != 0 ) // ((b & 1) != 0)
      {
      n = mulmod( n, a, m );
      }
    b = b.shiftRight(1);		// b >>= 1;
    a = mulmod( a, a, m );
    }
  return n;
  }

public static boolean b_SPRP(BigInteger n, int b)
  {
  BigInteger t = n.subtract(BigInteger.valueOf(1L));	// t = n-1
  BigInteger nMinus1 = t;
  BigInteger a = BigInteger.valueOf(0L);
  BigInteger test;

/*
Find t and a satisfying: n-1=2^a * t, t odd
*/
  while(((t.and(BigInteger.valueOf(1L))).compareTo(BigInteger.valueOf(0L))) == 0 ) // ( (t & 1) == 0 )
    {
    t = t.shiftRight(1);		// t >>= 1;
    a = a.add(BigInteger.valueOf(1L));			// a++;
    }
/*
We check the congruence class of b^((2^i)t) % n for each i from 0 to a - 1.
If any one is correct, then n passes. Otherwise, n fails.
*/
  test = modexpo(BigInteger.valueOf(b), t, n);
//  if( test == 1 || test == nMinus1 ) return true;
  if ( test.compareTo(BigInteger.valueOf(1L)) == 0 || test.compareTo(nMinus1) == 0 )
    return true;

  while ( a.compareTo(BigInteger.valueOf(1L)) > 0 )	// ( a > 1 )
    {
    a = a.subtract(BigInteger.valueOf(1L));		// a--;
    test = mulmod(test, test, n);
//    if( test == nMinus1 ) return true;
    if (test.compareTo(nMinus1) == 0)
      return true;
    }
  return false;
  }
}