/*
TASK:crazy
LANG:C++
*/
#include <stdio.h>
#include "module.h"

#define INF     (1000000)

int poss[512][512];
int isprime(int a) {if(poss[a][0]==0) return 1; else return 0;}
int dynf[512][512][2];

int nod(int a, int b){
    if(b==0) return a;
    else if(a>b) return nod(b,a-b);
    else return nod(a,b-a);
}

int f(int x, int y, int mm){
    int i, tmp;
    if(poss[x][0]==0&&poss[y][0]==0) {
      if(mm==0) return INF;
      else return 0;
    }
    if(dynf[x][y][mm]==-2*INF){
      if(mm==0){               //ako tyrsim pyrviq da bie...
         tmp=INF;
         for(i=0;poss[x][i]!=0;i++){
           if(f(poss[x][i],y+1,1)<tmp) tmp=f(poss[x][i],y+1,1);
         }
         for(i=0;poss[y][i]!=0;i++){
           if(f(x+1,poss[y][i],1)<tmp) tmp=f(x+1,poss[y][i],1);
         }
      }
      else{
         tmp=0;
         for(i=0;poss[x][i]!=0;i++){
           if(f(poss[x][i],y+1,0)>tmp) tmp=f(poss[x][i],y+1,0);
         }
         for(i=0;poss[y][i]!=0;i++){
           if(f(x+1,poss[y][i],0)>tmp) tmp=f(x+1,poss[y][i],0);
         }
      }
      dynf[x][y][mm]=tmp+1;
    }
    return dynf[x][y][mm];
}

void g(long x, long y, long *x1, long *y1){
    int i, min=INF;
    for(i=0;poss[x][i]!=0;i++){
      if(min>f(poss[x][i],y+1,1)) {
         min=f(poss[x][i],y+1,1);
         *x1=poss[x][i];
         *y1=y+1;
      }
    }
    for(i=0;poss[y][i]!=0;i++){
      if(min>f(x+1,poss[y][i],1)) {
         min=f(x+1,poss[y][i],1);
         *x1=x+1;
         *y1=poss[y][i];
      }
    }
}

int main(void){
    long x, y, x1, y1, i, j, k;
    //scanf("%d%d", &x, &y);
    for(i=2;i<501;i++) for(j=2,k=0;j<i;j++)
       if(nod(i,j)!=1) poss[i][k++]=j;
    /*for(i=2;i<13;i++) {
       for(j=0;poss[i][j]!=0;j++) printf("%d ", poss[i][j]);
       printf("\n");
    }*/
    for(i=0;i<512;i++) for(j=0;j<512;j++){
       dynf[i][j][0]=dynf[i][j][1]=-2*INF;
    }
    /*g(8,2, &x, &y); */
    while(1){
     getnum(&x,&y);
     g(x,y,&x1, &y1);
     setnum(x1,y1);
    }
    /*
    printf("RESULT:\n%d %d\n%d\n", x, y, f(x,y,0));*/
    return 0;
}
