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

#define MAX 15000
bool seen[MAX];
int unseen = 1;

bool isfib(int n) {
	return (n & (2*n))==0;
}

int compute(int n) {

	for (int k=unseen; k<MAX; k++) {
		if (!seen[k] && isfib(n * k)) {
			seen[k] = true;
			while (seen[unseen]) {
				unseen++;
			}

			return k;
		}
	}

	fprintf(stderr, "*** the end\n");
	exit(0);
}

int main() {
	memset(seen, 0, sizeof(seen));

	for (int n=1; n<=10000; n++) {
		printf("%d %d\n", n, compute(n));
		if (n%100==0) {
			fflush(stdout);
		}
	}

	return 0;
}