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

#define MAX 50000

bool ok(int n) {
	int s = 0;
	for (int r=2; n; r++) {
		int d = 1 << (n%r);
		if (s & d) {
			return false;
		}
		s += d;
		n /= r;
	}
	return true;
}

int *pos = 0;	// offset to next OK
int *nxt = 0;	// offset to next OK

bool seen[MAX];
int unseen = 1;

int other(int p) {
	seen[p] = true;
	while (seen[unseen]) {
		unseen++;
	}
	int v = unseen + pos[p+unseen];
	while (p+v<MAX) {
		if (!seen[v]) {
			return v;
		} else {
			v += nxt[p+v];
		}
	}

	printf("# the end\n");
	exit(1);
}

int main() {
	size_t s = MAX * sizeof(int);
	nxt = (int*)malloc(s);
	pos = (int*)malloc(s);

	if (nxt==0 || pos==0) {
		printf("# out of memory\n");
		exit(2);
	}

	memset(nxt, 0, s);
	memset(pos, 0, s);

	int p=0;
	for (int v=1; p<MAX; v++) {
		if (ok(v)) {
			for (int k=p+1; k<v && k<MAX; k++) {
				pos[k] = v-k;
			}
			nxt[p] = v-p;
			p = v;
		}
	}

	memset(seen, 0, sizeof(seen));
	int v=1;
	for (int n=1; n<=10000; n++) {
		printf("%d %d\n", n, v);
		v = other(v);
	}

	return 0;
}