#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;

#define MAX 10001

int a[MAX];
int visited[MAX];

int _gcd(int a, int b) {
    int temp;
    while (b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

#define OPT	1000
int gcdcache[OPT][OPT];

int gcd(int a, int b) {
	if (a<OPT && b<OPT) {
		return gcdcache[a][b];
	} else {
		return _gcd(a,b);
	}
}

int main() {
	for (int u=0; u<OPT;u++) {
		for (int v=0; v<OPT;v++) {
			gcdcache[u][v] = _gcd(u, v);
		}
	}

	memset(visited, -1, sizeof(visited));

	for (int n=1; n<MAX; n++) {
		for (int nk=n-1, n2k=n-2; n2k>0; nk-=1, n2k-=2) {
			int x = gcd(a[nk], a[n2k]);
			visited[x] = n;
		}

		int v=0;
		while (visited[v]==n) {
			v++;
		}

		printf("%d %d\n", n, a[n]=v);
		fflush(stdout);
	}

	return 0;
}