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

#define MAX 10000

// fills digits with the digits of n in base b
// digits[0] corresponds to the least digit
// returns the number of digits
int digits[1000];
int todigits(int n, int base) {
	int digitcount = 0;
	while (n) {
		digits[digitcount++] = n % base;
		n /= base;
	}
	return digitcount;
}

// numbers appearing in the concatenation of the last digits so far
int tail[ 1000];

// number seen so far ?
bool seen[1+MAX];

// A229123
int  a   [1+MAX];

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

	for (int base=2; base<=MAX; base++) {
		memset(seen, 0, sizeof(seen));
		int tailcount = 0;

		for (int n=1; n<=MAX; n++) {
			if (seen[n]) {
				a[n]++;
			}
			int digitcount = todigits(n, base);
			for (int d=digitcount-1; d>=0; d--) {
				int digit = digits[d];

				int newtailcount = 0;
				for (int t=0; t<tailcount; t++) {
					int newtail = tail[t]*base + digit;
					if (newtail <= MAX) {
						seen[newtail] = true;
						tail[newtailcount++] = newtail;
					}
				}
				if (digit) {
					seen[digit] = true;
					tail[newtailcount++] = digit;
				}
				tailcount = newtailcount;
			}
		}

		if (base % 100==0) {
			fprintf(stderr, "at base %d\n", base);
		}
	}

	for (int n=1; n<=MAX; n++) {
		printf("%d %d\n", n, a[n]);
	}

	return 0;
}