#include <iostream>
#include <string.h>

#define MAX 100000000

using namespace std;

long long prod[MAX];

#define WANTED 100000

long long first[WANTED];
int  unknown = 1;

int main() {
	memset(prod, 0, sizeof(prod));
	memset(first, 0, sizeof(first));
	first[1] = 1;

	int v = 1;
	int k = 0;

	long long pp = -1;

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

			if (ov>=MAX) {
				cerr << "# the end" << endl;
				return 1;
			}

			if (v<WANTED && !first[v]) {
				first[v] = n;
				while (first[unknown]) {
					cout << unknown << " " << first[unknown] << endl;
					unknown++;
					if (unknown==WANTED) {
						// got all
						return 0;
					}
				}
			}

			int old = prod[ov];
			if (old+1<=ov) {
				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;
}