/*
TASK:crazy
LANG:C
*/

#include <stdio.h>
#include <stdlib.h>

#include <time.h>

#include "module.h"

#define IN      "crazy.in"
#define OUT     "crazy.out"
#define MAX     512

#define LAST    425

long opes;

long x, y;

long all[MAX][MAX];
long *poss[MAX], num[MAX], primes[MAX], pnum, *list;
char done[MAX][MAX];
short prev[MAX][MAX][2];

long qend;
short queue[MAX*MAX][4];

long gcd(long a, long b)
{
   long r;

   r=a%b;
   while(r)
   {
      a=b;
      b=r;
      r=a%b;
   }

   return b;
}

int main()
{
   long i, j, next, nx, ny;

   clock();

   for(i=2; i<LAST; i++)
      for(j=i+1; j<LAST; j++)
         if(gcd(j, i)>1)
           num[i]++;

   for(i=2; i<LAST; i++)
   {
      poss[i]=(long*)malloc(sizeof(long)*num[i]);
      num[i]=0;
   }

   for(i=2; i<LAST; i++)
      for(j=i+1; j<LAST; j++)
         if(gcd(j, i)>1)
           poss[i][num[i]++]=j;

   for(i=2; i<LAST; i++)
   {
      for(j=2; j<i; j++)
         if(i%j==0) break;

      if(j==i)
        primes[pnum++]=i;
   }

   for(i=0; i<pnum; i++)
      for(j=0; j<pnum; j++)
      {
         queue[qend][0]=primes[i];
         queue[qend][1]=primes[j];
         queue[qend][2]=0;
         qend++;
         done[primes[i]][primes[j]]=1;
      }

   for(x=2; x<LAST; x++)
   {
      list=poss[x];
      
      for(y=2; y<LAST; y++)
      {
        if(y>2)
        {
          for(j=0; j<num[x]; j++)
             all[list[j]][y-1]++;
        }

        if(x>2)
        {
          for(j=0; j<num[y]; j++)
             all[x-1][poss[y][j]]++;
        }
      }
   }

//   printf("%ld T1 : %lf\n", opes, clock()/(double)CLOCKS_PER_SEC);

   for(i=0; i<qend; i++)
   {
      x=queue[i][0];
      y=queue[i][1];
      next=queue[i][2];

      if(y>2)
      {
        for(j=0; j<num[x]; j++)
        {
           nx=poss[x][j];
           all[nx][y-1]--;

           if(!done[nx][y-1] && (next==0 || all[nx][y-1]==0))
           {
             done[nx][y-1]=1;
             queue[qend][0]=nx;
             queue[qend][1]=y-1;
             queue[qend][2]=(next+1)%2;
             qend++;

             if(next==0)
             {
               prev[nx][y-1][0]=x;
               prev[nx][y-1][1]=y;
             }
           }
        }
      }

      if(x>2)
      {
        for(j=0; j<num[y]; j++)
        {
           ny=poss[y][j];
           all[x-1][ny]--;

           if(!done[x-1][ny] && (next==0 || all[x-1][ny]==0))
           {
             done[x-1][ny]=1;
             queue[qend][0]=x-1;
             queue[qend][1]=ny;
             queue[qend][2]=(next+1)%2;
             qend++;

             if(next==0)
             {
               prev[x-1][ny][0]=x;
               prev[x-1][ny][1]=y;
             }
           }
        }
      }
   }

//   printf("T2 : %lf\n", clock()/(double)CLOCKS_PER_SEC);

   while(1)
   {
     getnum(&x, &y);

     if(x>=LAST)
     {
       for(j=2; j<x; j++)
          if(gcd(x, j)>1)
          {
            setnum(j, y+1);
            goto END;
          }
     }
     else
       if(y>=LAST)
       {
         for(j=2; j<y; j++)
            if(gcd(y, j)>1)
            {
              setnum(x+1, j);
              goto END;
            }
       }
       else
         setnum(prev[x][y][0], prev[x][y][1]);

     END:;
   }

   return 0;
}

