import java.io.*;
import java.math.*;
//==========================================================C
//  OS(Quadratic Sieve) Function Program                    C
//  2次ふるい法javaプログラム ふるい改良１　                C
// 　　ふるいは倍精度浮動小数点を使用し、本来のふるい処理   C
//----------------------------------------------------------C
//   1. M = (int)sqrt(N)                                    C
//        using Bsqrt                                       C
//   2. Seting the Factor Base                              C
//        Prime Table:  PTB[NP]                             C
//        Factor Base:  FTB[NB]                             C
//   3. Sieving by QS                                       C
//     (1) Setting sieving base value                       C
//        Sieving base value: SBV[NS][3]                    C
//     (2) Sieving                                          C
//        Sieved Matrix: MQS[ND][NB]                        C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/08/15              C
//        ( Tokyo Kougei University )                       C
//        後 保範： 東京工芸大学                            C
//==========================================================C
public class QS2{
//==========================================================C
// Global data  (Constant and Work area)                    C
//==========================================================C
 public int PTB[] = new int[2000];
 public int FTB[] = new int[1000];
 public int SBV[][] = new int[3000][3];
 public double STB[][] = new double[2][1000000];
 public int MQS[][] = new int[1100][1000];
 public int AM[][] = new int[1100][1000];
 public int EM[][] = new int[1100][1000];
 public int LN[][] = new int[300][1000];
 public int PW[][] = new int[300][1000];
 public BigInteger MX[] = new BigInteger[1100];
 public BigInteger FactV[][] = new BigInteger[1000][4];
 public int NOS;
//==========================================================C
public BigInteger QS(BigInteger N, int NP, int LP, int NV[])
//==========================================================C
//  OS(Quadratic Sieve) Program                             C
//  2次ふるい法javaプログラム ふるい改良１　                C
//----------------------------------------------------------C
//    N       Bint, In,  Input Value for Factorizing        C
//    NP      int,  In,  Size of Prime Table                C
//    LP      int,  In,  Size of one sieve deta             C
//    NV[3]   int,  Out, NV[0]=NB, NV[1]=ND, NV[2]=NS       C
//    return  Bint, Out, M=sqrt(N)                          C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/08/15              C
//        ( Tokyo Kougei University )                       C
//        後 保範： 東京工芸大学                            C
//==========================================================C
 { int IWK[] = new int[100000];
   int NIWK = 100000, BV;
   int Debug = 0; 
// M = (int)sqrt(N)
   BigInteger M = Bsqrt(N);
   if(Debug==1) { System.out.println("M="+M.toString()); }
// Seting the Factor Base
   TPRIM(NP);
   int NB = BASE(N, NP);
//   BV = FTB[NB-1]*NB/2;
   BV = FTB[NB-1]*10;
   int NS = SBASE(N, M, NB, BV);
   if(Debug == 1) {
     for (int k=0; k<NB; k++)
       { System.out.println("k="+k+" "+FTB[k]); }
     for (int k=0; k<NS; k++)
       { System.out.println("SBV="+SBV[k][0]+" "+SBV[k][1]
                           +" "+SBV[k][2]); }
     } 
// Sieving by QS
   int ND = Qsieve(N, M, NB, NS, LP);
   NV[0] = NB;
   NV[1] = ND;
   NV[2] = NS;
   return M;}
//==========================================================C
public int Qsieve(BigInteger N, BigInteger M, int NB, 
                  int NS,int LP) 
//==========================================================C
//  Sieving by QS                                           C
//----------------------------------------------------------C
//    N       Bint, In,  Input Value for Factorizing        C
//    M       Bint, In,  M=sqrt(N)                          C
//    NB      int,  In,  Size of Factor Base (FTB[NB])      C
//    NS      int,  In,  Size of sieve base value (SBV)     C
//    LP      int,  In,  Size of one sieve deta             C
//    return  int,  out, Number of sieved data( > NB )      C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/08/15              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
{ int SV, ND=0;
  double DV[] = new double[2];
  BigInteger MS, BLP;
  String s1;
// Initial set
  s1 = Integer.toString(LP);
  BLP = new BigInteger(s1);
  s1 = N.toString();
  DV[0] = Double.parseDouble(s1);
  s1 = M.toString();
  DV[1] = Double.parseDouble(s1);
// Main Loop
  SV = 0;  MS = M;
  while (ND < NB)
//  Sieving by QS
   { Dsieve(DV, NS, SV, LP);
//  Select and set matrix
     ND = Ssieve(LP, ND, N, MS, NB);
     SV += LP;  MS = MS.add(BLP);
   }
 NOS = SV;
 return ND;}
//==========================================================C
public int Ssieve(int LP, int NO, BigInteger N,
       BigInteger MS, int NB)
//==========================================================C
//  Sieving by QS                                           C
//   select STB and set MQS(sieved matrix)                  C
//    STB[0][*] = X*X - N                                   C
//    STB[1][*] = multiply for base factor                  C
//----------------------------------------------------------C
//    LP      int,  In,  Size of one sieve deta             C
//    NO      int,  In,  Number of old selected sieve data  C
//    N       Bint, In,  Number for Factorizing             C
//    MS      Bint, In,  Start value (M+SV)                 C
//    NB      int,  In,  Size of Factor Base (FTB[NB])      C
//    return  int,  out, Number of new selected sieve data  C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/08/15              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
{ int k, j, NN;
  int PW[] = new int[2100];
  double VL;
  BigInteger One = new BigInteger("1");
  BigInteger X, X2;
// Initial set
  X = MS;  NN = NO;
  VL = FTB[NB-1];
// Main Loop
  for (k=0; k<LP; k++)
//  Select
   { if(STB[0][k] < STB[1][k]*VL)
//  Set MQS
      { X2 = X.multiply(X);
        X2 = X2.subtract(N); 
        BigInteger NF = BFact(X2, NB, PW);
        if(NF.compareTo(One) == 0)
         { for (j=0; j<NB; j++)
            { MQS[NN][j] = PW[j]; }
           MX[NN] = X;  NN++;
         }
      }
     X = X.add(One);
   }
  return NN; }
//==========================================================C
public void Dsieve(double DV[], int NS, int SV, int LP)
//==========================================================C
//  Sieving by QS                                           C
//   set STB(Sieving table) using                           C
//    STB[0][*] = X*X - N                                   C
//    STB[1][*] = multiply for base factor                  C
//----------------------------------------------------------C
//    DV[2]   dbl,  In,  N=DV[0], M=DV[1]                   C
//    NS      int,  In,  Size of SBV(Sieving base value)    C
//    SV      int,  In,  Start Value for sieving            C
//    LP      int,  In,  Size of one sieve deta             C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/08/15              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
{ int k, j, Q, ST;
  double DN, DM, X, P;
// Initial set
  DN = DV[0];  DM = DV[1];
  for (j=0; j<LP; j++)
   { X = DM + (SV + j);
     STB[0][j] = X*X - DN;
     STB[1][j] = 1.0;  }
// Main Loop
  for (k=0; k<NS; k++)
    { P = SBV[k][0];
      Q = SBV[k][1];
      ST = SBV[k][2];
      ST = (ST - SV)%Q;
      if(ST < 0) ST += Q;
      for (j=ST; j<LP; j=j+Q)
       { STB[1][j] *= P;  }
    }
 }
//==========================================================C
public void TPRIM(int NP)
//==========================================================C
//  Setting the Table of Prime Numbers                      C
//   PTB(k) = k's Prime Number                              C
//     k=0,1,...,NP-1,  PTB(1)=2, PTB(2)=3, PTB(3)=5,...    C
//----------------------------------------------------------C
//    NP     int, In,  Size of Prime Table                  C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/01/12              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
{ int i, j, j1,k;
  int IWK[] = new int[10000];
  int NIWK=10000;
  int NO, LPM, NE, NH, NS, NS1; 
  int NIT[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43};
//  Initial Set
  NO = 14;  LPM = 43;
  for (i=0; i<Math.min(NO,NP); i++)
    { PTB[i] = NIT[i]; }
//  Main Loop of prime numbers
  for (k=1; k<=10000; k++)
    { if(NP <= NO) { break; }
      NE = NIWK;
      if(LPM <= 30000) NE = Math.min(LPM*LPM/2, NIWK);
      for (i=0; i<NE; i++)
        { IWK[i] = 0; }
//  Set odd composit number
      NH = LPM + 2*NE;
      for (j1=1; j1<NO; j1++)
        { j = PTB[j1];
          if(j*j > NH) { break; }
          NS1 = j - (LPM+2)%j;
          if(NS1 == j) { NS1 = 0; }
          NS  = (j*(NS1%2) + NS1)/2;
          for (i=NS; i<NE; i+=j)
            { IWK[i] = 1; }
        }
//  Search prime number
      for (i=0; i<NE; i++)
        { LPM = LPM + 2;
          if(IWK[i] == 0) 
            { PTB[NO] = LPM;
              NO += 1; }
          if(NO >= NP) { break; }
        }
     }
  }
//==========================================================C
public BigInteger BFact(BigInteger X, int NB, int PW[])
//==========================================================C
//  Factorization with Primes                               C
//    X=FTB[0]^PW[0]*...*FTB[N-1]*PW[N-1]*Y                 C
//----------------------------------------------------------C
//   X         Big, In,  Target value                       C
//   NB        int, In,  Size of Factor Base                C
//   PW[NP]    int, Out, Power of Factor Base               C
//   return    Big, Out, No factorized value (Y)            C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2007/12/31              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
{ BigInteger Y, PK, P0;
  BigInteger Zero = new BigInteger("0");
  Y = X;
// Main Loop
  for (int k=0; k<NB; k++)
    { int IP = FTB[k];  PW[k] = 0;
      String s1 = Integer.toString(IP);
      PK = new BigInteger(s1);
      for ( int j=0; j<20; j++)
        { P0 = Y.mod(PK);
          int IT = P0.compareTo(Zero);
          if(IT == 0) 
            { PW[k] += 1;
              Y = Y.divide(PK); }
          else { break; } 
    }   }
  return Y; }
//==========================================================C
public int SBASE(BigInteger N, BigInteger M, int NB, int MV) 
//==========================================================C
//  Setting SBV: Sieving base vale                          C
//    if(S^2 - N (mod P^l) == 0) --> set SBV                C
//      SBV[*][0] = P in FTB                                C
//      SBV[*][1] = Q = P^l (l=1,2,...)                     C
//      SBV[*][2] = M-S (mod Q) (0 =< S < Q)                C
//----------------------------------------------------------C
//    N       Bint, In,  Input Value for Factorizing        C
//    M       Bint,In,  M=sqrt(N)                           C
//    NB      int, In,  Size of Factor Base                 C
//    MV      int, In,  Maximum value for sieving value     C
//    return  int, Out, Size of SBV(Sieving base value)     C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/08/15              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
{ int NS = 0;
  int k, j, S2, Nin;
  int P, Q, IM;
//  main Loop
  for (k=0; k<NB; k++)
    { P = FTB[k];
      Q = P;
      while (Q <= MV)
       { Nin = Bmodi(N, Q);
         IM  = Bmodi(M, Q);
         for (j=0; j<Q; j++)
          { S2 = (j+IM)*(j+IM) - Nin;
            S2 = S2%Q;
            if(S2 < 0) S2 += Q;
            if(S2 == 0) 
             { SBV[NS][0] = P;
               SBV[NS][1] = Q;
               SBV[NS][2] = j;
               NS++; }
          }
         Q *= P;
       }
    }  
  return NS; }
//==========================================================C
public int BASE(BigInteger N, int NP) 
//==========================================================C
//  Setting FTB: Factor Base                                C
//    if(S^2 - N (mod P) == 0) --> set FTB                  C
//----------------------------------------------------------C
//    N       Bint, In,  Input Value for Factorizing        C
//    NP      int, In,  Size of Prime Table                 C
//    return  int, Out, Size of Factor Base                 C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/01/12              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
{ int NB = 0;
  int k, j, S2, Nin;
//  main Loop
  for (k=0; k<NP; k++)
    { int P = PTB[k];
      Nin = Bmodi(N, P);
      for (j=0; j<P; j++)
        { S2 = j*j - Nin;
          if(S2%P == 0) 
            { FTB[NB] = P;  NB++;
              break; }
        }
    }  
  return NB; }
//==========================================================C
public int Bmodi(BigInteger X, int Y) 
//==========================================================C
//  Z = X (mod Y)                                           C
//    X: BigInteger,  Y,Z: int                              C
//----------------------------------------------------------C
//    X       Bint, In,  First input value                  C
//    Y       int,  In,  Second input value                 C
//    return  int,  Out, Z = X (mod Y)                      C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/01/12              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
{ int Z;
  BigInteger BY, BZ;
  String s1;
  s1 = Integer.toString(Y);
  BY = new BigInteger(s1);
//  Z = X (mod Y)
  BZ = X.mod(BY);
  s1 = BZ.toString();
  Z  = Integer.parseInt(s1);
  if(Z < 0) Z += Y;
  return Z;  }
//==========================================================C
//  Bsqrt(x) : Sqrt for x of BigInteger                     C
//----------------------------------------------------------C
//   x        Bint, In,  Input integer value                C
//   return   Bint, Out, Integer sqrt(x)                    C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/07/27              C
//        ( Tokyo Polytechnic University )                  C
//==========================================================C
 public BigInteger Bsqrt(BigInteger x)
  { BigInteger u, w, t, TEN, One, Zero;
    int  k, n, m;
    Zero = new BigInteger("0");
    One  = new BigInteger("1");
    TEN  = new BigInteger("10");
//  double xs=sqrt(x) 
    String x1 = x.toString();
    double xd = Double.parseDouble(x1);
    double xs = Math.sqrt(xd);
//  int 10**(9*n)*is=sqrt(x)
    n = 0;
    for (k=0; k<=150; k++) {
       if(xs <= 1.0e9) break;
       n = n + 1;
       xs = xs/10.0; }
    int ix = (int)xs;
    String ss = Integer.toString(ix);
//  BigInteger t = a start value of sqrt(x) 
    t = new BigInteger(ss);
    for (k=1; k<=n; k++)
      { t = t.multiply(TEN); }
//  Loop Number for Newton Method
    m = 4;
    if(n >=8) m = 6; 
    if(n >=30) m = 8;
//  BigInteger t = sqrt(x) by Newton Method
    if(t.compareTo(Zero) != 0) {
      for (k = 1; k <= m; k++)
        { w = t.multiply(t);
          u = w.add(x);
          w = t.add(t);
          t = u.divide(w); }  }
    t = t.add(One);
    return t; }
//==========================================================C
//  Gauss Elimination Program with 0-1                      C
//    Make matrix AM(0-1) from MQS & EM(unit)               C
//    Gauss Elimination A+E                                 C
//      A=AM[N][M],  E=EM[N][N]                             C
//----------------------------------------------------------C
//   N         int,  in,  Number of rows for AM, EM         C
//   M         int,  in,  Number of columns for AM          C
//   return int,  Out, ID >= 1; Number of dependency        C
//                         = 0; no-dependency               C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/07/27              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
 public int Gauss(int N, int M) throws Exception 
{ int ID, IP, IW;
  int k, j, i, KM, kk;
  int IO=0;
// Setting Output File
  FileOutputStream fo = new FileOutputStream("Gauss.txt");
  PrintWriter out = new PrintWriter(fo,true);
// Make matrix AM(0-1) from MQS & EM(unit)
  for (k=0; k<N; k++)
   { for (j=0; j<M; j++)
      { AM[k][j] = MQS[k][j]%2; }
     for (j=0; j<N; j++)
      { EM[k][j] = 0; }
     EM[k][k] = 1;
   }
//  Output Matrix
  if(IO >=1)
   { out.println("Input");
     for (i=0; i<N; i++)
      { out.print(i+"  ");
        for (j=0; j<M; j++)
         { out.print(AM[i][j]+" "); }
        for (j=0; j<N; j++)
         { out.print(" "+EM[i][j]); }
        out.println("");
      } 
   } 
// Gauss Elimination
  KM = 0;  kk = 0;
  for (k=0; k<M; k++)
   { if(kk > KM) KM = kk;
     IP = 0;
     if(AM[kk][k] == 0) {
//  Search Pivot
       IP = -1;
       for (i=kk+1; i<N; i++)
         { if(AM[i][k] == 1) 
            { IP = i;  break; }
         }
//    System.out.println("AM="+AM[kk][k]+" k="+k+" kk="+kk+" IP="+IP);
//  Exchange row for kk <--> IP
       if(IP > KM) KM = IP;
       if(IP != -1)
        { for (j=k; j<M; j++)
           { IW = AM[IP][j];
             AM[IP][j] = AM[kk][j];
             AM[kk][j] = IW; }
          for (j=0; j<=KM; j++)
           { IW = EM[IP][j];
             EM[IP][j] = EM[kk][j];
             EM[kk][j] = IW; }  }
      }
//  if(k-column vector is all zero) --> skip 
    if(IP != -1) {
       for (i=kk+1; i<N; i++)
        { if(AM[i][k] == 1)
//  Elimination of AM
           { for (j=k+1; j<M; j++)
              { AM[i][j] = AM[i][j]^AM[kk][j]; }
//  Elimination of EM
             for (j=0; j<=KM; j++)
              { EM[i][j] = EM[i][j]^EM[kk][j]; }
           }
        } 
//  Output Matrix
       if(IO >=1)
        { out.println(kk);
          for (i=kk; i<N; i++)
           { out.print(i+"  ");
             for (j=0; j<M; j++)
              { out.print(AM[i][j]+" "); }
             for (j=0; j<N; j++)
              { out.print(" "+EM[i][j]); } 
             out.println("");
           } 
        } 
//  Clear k-coumn of AM
       for (i=kk+1; i<N; i++)
        { AM[i][k] = 0; }
//  count up kk
       kk++; }
   }
// Number of Dependency
  ID = 0;
  if(N-kk > 0) { ID = N - kk; }
  return ID; }
//==========================================================C
//  Factor : Factorizeing by the QS                         C
//    using:  MQS[N][M], EM[N][N], FTB[M]                   C
//    output: LN[NO][], PW[NO][M]                           C
//----------------------------------------------------------C
//   NV      Bint, In,  Input Value for Factorizing         C
//   MV      Bint, In,  MV=sqrt(NV), Number of QS starting  C
//   N       int,  In,  Number of rows for MQS, EM          C
//   M       int,  In,  Number of columns for EM            C
//   NO      int,  In,  Number of factorized value          C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/07/31              C
//        ( Tokyo Polytechnic University )                  C
//==========================================================C
 public void Factor(BigInteger NV, BigInteger MV,
             int N, int M, int NO)
 { int k, j, i, NN, NOP, CN;
   BigInteger X, Y, XV, YV, YI;
   BigInteger One = new BigInteger("1");
   String s1;
//  Set to dependet column
   for (k=0; k<NO; k++)
    { NN = 0;
      for (j=0; j<N; j++)
       { if(EM[N-NO+k][j] == 1)
          { NN++;  LN[k][NN] = j;  } }
      LN[k][0] = NN; 
    }
//  Set to power of base-factorr
   for (k=0; k<NO; k++)
    { NOP = LN[k][0];
//  Set to PW
      for (i=0; i<M; i++)
       { PW[k][i] = 0; }
      for (j=1; j<=NOP; j++)
       { CN = LN[k][j];
         for (i=0; i<M; i++)
          { PW[k][i] += MQS[CN][i]; }
       }
//  Compute X, Y with X^2=Y^2 (mod NV)
      X = One;  Y = One;
      for (j=1; j<=NOP; j++)
       { CN = LN[k][j];
//   Compute X
         XV = MX[CN];
         X  = X.multiply(XV);
         X  = X.mod(NV); }
//   Compute Y
      for (i=0; i<M; i++)
       { int IPW = PW[k][i]/2;
         if(IPW >= 1) 
          { s1 = Integer.toString(IPW);
            YI = new BigInteger(s1);
            s1 = Integer.toString(FTB[i]);
            YV = new BigInteger(s1);
            YV = YV.modPow(YI, NV);
            Y  = Y.multiply(YV);
            Y  = Y.mod(NV);  }
       }
      FactV[k][0] = X;
      FactV[k][1] = Y;
//   Comput GCD(X+Y,NV) and GCD(X-Y,NV)
      XV = X.add(Y);
      X  = XV.gcd(NV);
      Y  = NV.divide(X);
      FactV[k][2] = X;
      FactV[k][3] = Y;
    }
  }
 }