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

using namespace std;

#define MAX (10000+1)

int tab[MAX];	// sieve for prime numbers and exploration marks
int pi [MAX];
int v = 0;

void explore(int n, int k) {
	if (tab[k]!=n) {
		tab[k] = n;
		v++;
		explore(n, pi[k]);
		explore(n, k-pi[k]);
	}
}

int main() {
	memset(tab, 0, sizeof(tab));
	memset(pi,  0, sizeof(pi));
	tab[1] = -1;

	int pc = 0;

	for (int n=1; n<MAX; n++) {
		if (!tab[n]) {
			pc++;
			for (int m=2*n; m<MAX; m+=n) {
				tab[m] = -1;
			}
		}
		pi[n] = pc;

		tab[1] = n;
		v = 1;
		explore(n, n);

		cout << n << " " << v << endl;
	}
	
	return 0;
}