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

#define MAX 100000000

long long prod[MAX];

#define WANTED 10001
long long a[WANTED];
int u = 1;

int main() {
	memset(prod, 0, sizeof(prod));
	memset(a, 0, sizeof(a));

	int v = 1;
	int k = 0;
	int m = 0;
	long long p = -1;
	long long pp = -1;
	int f = 0;

	for (long long n=1; n<=1000000000000000000ll; n++) {
		for (int o=1;; o++) {
			int ov = o*v;

			if (ov>=MAX) {
				fprintf(stderr, "#the end\n");
				return 1;
			}

			int old = prod[ov];
			if (old+1<=ov) {
				if (!old && ov<WANTED) {
					a[ov]=n;
					while (a[u]) {
						printf("%d %lld\n", u, a[u]);
						fflush(stdout);
						u++;
						if (u==WANTED) {
							return 0;
						}
					}
				}

				v=o;

				if (pp==ov) {
					// giant step - the sequence is 2-periodic for a while
					if ((ov-old)%2==0) {
						v = ov/o;
					}
					prod[ov] = ov;
					n += ov-old-1;
				} else {
					prod[ov] = old+1;
					pp = ov;
				}

				break;
			}
		}
	}

	return 0;
}