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

#define K	2			// a[1] = ... = a[K] = 1
#define MAX 10000+1

int pi[MAX];
int a[MAX];

int main() {
	memset(pi, 0, sizeof(pi));
	memset(a, 0, sizeof(a));

	int *sieve = a;
	int pc = 0;
	sieve[1] = 1;

	for (int n=1; n<MAX; n++) {
		if (!sieve[n]) {
			pc++;
			for (int m=n; m<MAX; m+=n) {
				sieve[m] = 1;
			}
		}

		pi[n] = pc;

		if (n<=K) {
			a[n] = 1;
		} else {
			a[n] = a[pi[n]] + a[n-pi[n]];
		}

		std::cout << n << " " << a[n] << std::endl;
	}

	return 0;
}