#include <stdio.h>

#define MAX 1+1000000

int a[MAX];

void explore(int index, int x, int y) {
	int xy = x+y;
	if (xy<MAX) {
		if (a[xy] > index) {
			a[xy] = index;
		}
		explore(index, y, xy);
	}
}

int main() {
	for (int n=0; n<MAX; n++) {
		a[n] = n;
	}

	for (int f0=1; f0<MAX; f0++) {
		for (int f1=1; f0*f1<MAX; f1++) {
			explore(f0*f1, f0, f1);
		}
	}

	for (int n=1; n<MAX; n++) {
		printf("%d %d\n", n, a[n]);
	}

	return 0;
}