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

#define MAX 25000000

std::vector<int> primes;
int sieve[1+MAX];
int seen[1000];

int main() {
	memset(sieve, 0, sizeof(sieve));
	sieve[1]=1;
	for (int n=2; n<=MAX; n++) {
		if (!sieve[n]) {
			primes.push_back(n);
			int p = primes.size();
			int m = n;
			while (m<=MAX) {
				sieve[m] = p;
				m += n;
			}
		}

		// sieve contains:
		// - before n: a(n)
		// - at n: the 1-based index of a prime dividing n

		int prime = primes[sieve[n]-1];
		sieve[n] = sieve[n/prime] * (prime-sieve[n]);
	}

	memset(seen, 0, sizeof(seen));
	sieve[1] = 0;
	for (int n=2; n<=MAX; n++) {
		if (sieve[n]==1) {
			sieve[n] = 0;
		} else {
			sieve[n] = 1+sieve[sieve[n]];
			if (!seen[sieve[n]]) {
				seen[sieve[n]] = n;
				printf("%d %d\n", sieve[n], n);
			}
		}
	}

	return 0;
}