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

#define LST 1023456789	// last term
#define MAX (LST+1)
short *mask = 0;		// n -> mask of digits in n

short dig[10];			// 1<<d
int lst[10];			// least number with digit d not yet seen

int other(int n, int v) {
	short m = mask[v];
	mask[v] = 0;

	for (int d=0; d<10; d++) {
		if (lst[d]==v) {
			do {
				lst[d]++;
			} while ((mask[lst[d]] & dig[d])==0);
		}
	}

	int w = LST;

	for (int d=0; d<10; d++) {
		if ((m & dig[d])==0) {
			if (w > lst[d]) {
				w = lst[d];
			}
		}
	}

	return w;
}

int main() {
	mask = new short[MAX];

	for (int n=0; n<10; n++) {
		lst[n] = n;
		mask[n] = dig[n] = (1 << n);
	}
	for (int n=10; n<MAX; n++) {
		mask[n] = mask[n/10] | (1 << (n%10));
	}

	int v = 0;
	for (int n=0; n<=10000; n++) {
		if (n) {
			printf("%d %d\n", n, v);
		}
		if (v==LST) {
			break;
		} else {
			v = other(n, v);
		}
	}

	delete[] mask;

	return 0;
}