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

#define MAX (1LL<<32)

char *omega = 0;
bool *sfull = 0;

#define MAXR 100
long long a[MAXR];

int main() {
	omega = new char[MAX];
	sfull = new bool[MAX];

	memset(omega, 0, MAX*sizeof(*omega));
	memset(sfull, 0, MAX*sizeof(*sfull));

	memset(a, 0, sizeof(a));
	long long n0, w = 0, u = 1;
	bool over2 = false;	// n^2 > MAX?

	for (long long n=2; n<MAX; n++) {
		if (!omega[n]) {
			for (long long m=n; m<MAX; m+=n) {
				omega[m]++;
			}
			if (!over2) {
				long long n2 = n*n;
				if (n2<MAX) {
					for (long long s=n2; s<MAX; s+=n2) {
						sfull[s] = true;
					}
				} else {
					over2 = true;
				}
			}
		}

		if (sfull[n] && omega[n]>1) {
			if (w==0) {
				// start of a new run of terms of A126706
				n0 = n;
			}
			w++;
		} else {
			if (w<MAXR && a[w]==0) {
				a[w] = n0;
				while (u<MAXR && a[u]) {
					printf("%lld %lld\n", u, a[u]);
					fflush(stdout);
					u++;
				}
			}
			w = 0;
		}
	}

	delete[] omega;
	delete[] sfull;

	return 0;
}