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

#define MAX 100000000LL
long long *prod = 0;	// [MAX];

#define WANTED 100000000LL
long long *a = 0;	// [WANTED];	// first index
long long *b = 0;	// [WANTED];	// last index
int u = 1;
int r = 0;
int mx = -1;

int main() {
	prod = (long long*)malloc(MAX*sizeof(*prod));
	a = (long long*)malloc(MAX*sizeof(*a));
	b = (long long*)malloc(MAX*sizeof(*b));

	memset(prod, 0, sizeof(prod));
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));

	int v = 1;
	int k = 0;

	int m = 0;
	long long p = -1;
	long long pp = -1;

	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;
				}

				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;
				}

				if (prod[ov]==ov && ov<WANTED) {
					b[ov] = n;

					while (b[u]) {
						int w = b[u]-a[u]+1;
						if (mx<w) {
							mx=w;
							printf ("%d %lld\n", ++r, u);
							fflush(stdout);
						}

						if (++u==WANTED) {
							return 0;
						}
					}
				}

				break;
			}
		}
	}

	return 0;
}