import java.io.*;
import java.math.*;
//==========================================================C
//  OS(Quadratic Sieve) Program                             C
//  2次ふるい法javaプログラム 原理プログラム                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
//        Sieved Matrix: MQS[ND][NB]                        C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/07/27              C
//        ( Tokyo Kougei University )                       C
//        後 保範： 東京工芸大学                            C
//==========================================================C
public class QS{
//==========================================================C
// Global data  (Constant and Work area)                    C
//==========================================================C
 public int PTB[] = new int[500];
 public int FTB[] = new int[250];
 public int MQS[][] = new int[300][250];
 public int AM[][] = new int[300][250];
 public int EM[][] = new int[300][250];
 public int LN[][] = new int[30][150];
 public int PW[][] = new int[30][250];
 public BigInteger MX[] = new BigInteger[300];
 public BigInteger FactV[][] = new BigInteger[30][4];
 public int NOS;
//==========================================================C
public BigInteger QS(BigInteger N, int NP, int NV[])
//==========================================================C
//  OS(Quadratic Sieve) Program                             C
//----------------------------------------------------------C
//    N       Bint, In,  Input Value for Factorizing        C
//    NP      int,  In,  Size of Prime Table                C
//    NV[2]   int,  Out, NV[1]=NB, NV[2]=ND                 C
//    return  Bint, Out, M=sqrt(N)                          C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/07/27              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
 { int IWK[] = new int[10000];
   int NIWK = 10000;
   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); 
   if(Debug==1) {
     for (int k=0; k<NB; k++)
       { System.out.println("k="+k+" "+FTB[k]); }
     } 
// Sieving by QS
   int ND = Qsieve(N, M, NB);
   NV[0] = NB;
   NV[1] = ND;
   return M;}
//==========================================================C
public int Qsieve(BigInteger N, BigInteger M, int NB)
//==========================================================C
//  Sieving by QS                                           C
//   set MQS[ND][NB]                                        C
//----------------------------------------------------------C
//    N       Bint, In,  Number of Factorized               C
//    M       Bint, In,  M=sqrt(N)                          C
//    NB      int,  In,  Size of Factor Base (FTB[NB])      C
//    return  int,  out, Number of sieved data(NB+1)        C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/01/12              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
{ int k, ND=0;
  int PW[] = new int[500];
  BigInteger X2, X;
  BigInteger One = new BigInteger("1");
  X = M;  NOS = 0;
  while(ND < NB+1)
    { X2 = X.multiply(X);
      X2 = X2.subtract(N);
      BigInteger NO = BFact(X2, NB, PW);
      if(NO.compareTo(One) == 0) 
        { for (k=0; k<NB; k++)
            { MQS[ND][k] = PW[k]; }
          MX[ND] = X;  ND++;
        }
      X = X.add(One);  NOS++;
    }
 return ND;}
//==========================================================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 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,  Number of Factorized                 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) {
//  Elimination of AM
       for (j=k+1; j<M; j++)
        { if(AM[kk][j] == 1)
           { for (i=kk+1; i<N; i++)
              { AM[i][j] = AM[i][j]^AM[i][k]; }
           }
        } 
//  Elimination of EM
       for (j=0; j<=KM; j++)
        { if(EM[kk][j] == 1)
           { for (i=kk+1; i<N; i++)
              { EM[i][j] = EM[i][j]^AM[i][k]; }
           }
        }
//  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;
    }
  }
 }