/*
TASK: crazy
LANG: C
*/

#include <stdio.h>
#include <math.h>
#include "module.h"

#define N       512

int p[N];
int pc;

short m[N][N][2];
int c[N][N];
char w[N][N];
int q[N*N];
int qb, qe;

void genp() {
	int i, j;
	
	p[0] = 2;
	pc = 1;

	for (i = 3; i < N; i++) {
		for (j = 0; p[j] <= sqrt(i); j++)
			if (i % p[j] == 0)
				break;
                if (i % p[j] == 0)
			continue;
                p[pc++] = i;
	}
}

void solve() {
	int i, j, k, l;
	long a1, b1, a2, b2;
          
	for (i = 2; i < N; i++) {
                for (j = i; j < N; j++) {
			for (k = 0; k < pc; k++) {
				if (i%p[k] != 0) continue;
                                for (l = (i/p[k]) + 1; l*p[k] < N; l++) {
                                        if (l*p[k] > j-1)
                                                c[j-1][l*p[k]]++;
                                        else
                                                c[l*p[k]][j-1]++;
                                }
                        }
					
			for (k = 0; k < pc; k++) {
				if (j%p[k] != 0) continue;
                                for (l = (j/p[k]) + 1; l*p[k] < N; l++) {
                                        if (i-1 > l*p[k])
                                                c[l*p[k]][i-1]++;
                                        else
                                                c[i-1][l*p[k]]++;
                                }
                        }
		}
        }

	qb = qe = 0;
	for (i = 0; i < pc; i++)
                for (j = i; j < pc; j++) {
			w[p[i]][p[j]] = 2;
			q[qe++] = p[i]*N + p[j];
                }

	while (qb < qe) {
		i = q[qb]/N;
		j = q[qb]%N;
		qb++;
                
		if (w[i][j] == 2) {
			for (k = 0; k < pc; k++) {
				if (i%p[k] != 0) continue;
				for (l = (i/p[k]) + 1; l*p[k] < N; l++) {
                                        if (l*p[k] > j-1) {
                                                if (w[j-1][l*p[k]] != 0) continue;
                                                w[j-1][l*p[k]] = 1;
                                                m[j-1][l*p[k]][0] = j;
                                                m[j-1][l*p[k]][1] = i;
                                                q[qe++] = (j-1)*N + l*p[k];
                                        } else {
                                                if (w[l*p[k]][j-1] != 0) continue;
					
                                                w[l*p[k]][j-1] = 1;
                                                m[l*p[k]][j-1][0] = i;
                                                m[l*p[k]][j-1][1] = j;
                                                q[qe++] = l*p[k]*N + j - 1;
                                        }
                                }
                        }

			for (k = 0; k < pc; k++) {
				if (j%p[k] != 0) continue;
				for (l = (j/p[k]) + 1; l*p[k] < N; l++) {
                                        if (i-1 > l*p[k]) {
                                                if (w[l*p[k]][i-1] != 0) continue;
					
                                                w[l*p[k]][i-1] = 1;
                                                m[l*p[k]][i-1][0] = j;
                                                m[l*p[k]][i-1][1] = i;
                                                q[qe++] = l*p[k]*N + i - 1;

                                        } else {
                                                if (w[i-1][l*p[k]] != 0) continue;

                                                w[i-1][l*p[k]] = 1;
                                                m[i-1][l*p[k]][0] = i;
                                                m[i-1][l*p[k]][1] = j;
                                                q[qe++] = (i-1)*N + l*p[k];
                                        }
                                }
	                }
                } else {
                        for (k = 0; k < pc; k++) {
				if (i%p[k] != 0) continue;
				for (l = (i/p[k]) + 1; l*p[k] < N; l++) {
                                        if (l*p[k] > j-1) {
                                                c[j-1][l*p[k]]--;
                                                if (c[j-1][l*p[k]] == 0) {
                                                        w[j-1][l*p[k]] = 2;
                                                        q[qe++] = (j-1)*N + l*p[k];
                                                }
                                        } else {
                                                c[l*p[k]][j-1]--;

                                                if (c[l*p[k]][j-1] == 0) {
                                                        w[l*p[k]][j-1] = 2;
                                                        q[qe++] = l*p[k]*N + j - 1;
                                                }
                                        } 
                                }
                        }        
					
			for (k = 0; k < pc; k++) {
				if (j%p[k] != 0) continue;
				for (l = (j/p[k]) + 1; l*p[k] < N; l++) {
                                        if (i-1 > l*p[k]) {
                                                c[l*p[k]][i-1]--;

                                                if (c[l*p[k]][i-1] == 0) {
                                                        w[l*p[k]][i-1] = 2;
                                                        q[qe++] = l*p[k]*N + i - 1;
                                                }
                                        } else {
                                                c[i-1][l*p[k]]--;
                                                if (c[i-1][l*p[k]] == 0) {
                                                        w[i-1][l*p[k]] = 2;
                                                        q[qe++] = (i-1)*N + l*p[k];
                                                }
                                        }
				}
	                }
                }  
	}

	while (1) {
		getnum(&a1, &b1);
                if (a1 > b1) {
                        a2 = (long) m[b1][a1][1];
                        b2 = (long) m[b1][a1][0];
                } else {
                        a2 = (long) m[a1][b1][0];
                        b2 = (long) m[a1][b1][1];
                }
		setnum(a2, b2);
	}
}

int main() {
	genp();
	solve();
	return 0;
}
