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

#define MAX 50000000

int *tau = 0;
bool *is = 0;

int f(int n) {
	for (int k=0; n<MAX; k++, n+=tau[n]) {
		if (is[n]) {
			return k;
		}
	}

	return -1;	// the end
}

int main() {
	tau = (int*) malloc(MAX * sizeof(*tau));
	is = (bool*) malloc(MAX * sizeof(*is));

	if (!tau || !is) {
		fprintf(stderr, "# out of memory\n");
		return 1;
	}

	memset(tau, 0, MAX * sizeof(*tau));
	memset(is, 0, MAX * sizeof(*is));

	for (int n=1; n<MAX; n++) {
		for (int m=n; m<MAX; m+=n) {
			tau[m]++;
		}
	}

	int w = 1;
	while (w<MAX) {
		is[w] = true;
		w += tau[w];
	}

	int k = 0;
	int mx = -1;
	for (int n=1; n<MAX; n++) {
		int v = f(n);
		if (v<0) {
			break;	// the end
		}

		if (mx < v) {
			mx = v;
			printf("%d %d\n", ++k, mx);
			fflush(stdout);
		}
	}

	free(tau);
	free(is);

	return 0;
}