Given a positive integer n, your task is to find a positive integer m, which is a multiple of n, and that m contains the least number of different digits when represented in decimal. For example, number 1334 contains three different digits 1, 3 and 4.

Input 

The input consists of no more than 50 test cases. Each test case has only one line, which contains a positive integer n ( 1n < 65536). There are no blank lines between cases. A line with a single `0' terminates the input.

Output 

For each test case, you should output one line, which contains m. If there are several possible results, you should output the smallest one. Do not output blank lines between cases.

Sample Input 

7 
15 
16 
101 
0

Sample Output 

7 
555 
16 
1111

找到一個用最少位數種類表示的十進制數字可以被 n 整除。
如果最少位數種類相同時，則選擇一個最小的數字。

題目解法：

根據離散數學，每個數字的倍數一定可以表示成由 0 和 1 構成的數字。
那麼可以保證最大上限的最少位數種類為 2。

根據題目意思，優先查找只能由 1 種構成的數字，採用查找循環節的 O(n) 算法。

當嘗試不出來時，開始窮舉湊成的 2 種構成，使用 BFS 的思路，只要優先對最小的拓展，
第一個查找出來的數字必然是由這 2 個數字構成的最小數字。

至於寫法有點不明確，但仍然得到 Accept。

稍微說明一下我的疑惑，假設兩個數字分別為 2 和 0，
數字開頭肯定是 20XXXXX...，但是對於 BFS 搜索時，會出現 220XXXX 是解。
由於我沒有額外檢查字典順序，可能在相同長度情況下 21XXXXX 會比較小 (接下來窮舉 2, 1)
此時輸出就會錯誤。


#include <stdio.h> 
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int single(int d, int n) {
	int mark[65536] = {};
	int i = d%n, j = 1;
	if(i == 0)	return 1;
	for(j++; ; j++) {
		i = (i*10 + d)%n;
		if(i == 0)	return j;
		if(mark[i] == 1)	return -1;
		mark[i] = 1;
	}
}
char buffer[65536*2];
char ret[65536*2];
int combine(int d1, int d2, int n) {
	if((d1*10 + d2)%n == 0) {
		buffer[0] = d2, buffer[1] = d1;
		return 2;
	}
	int prev[65536][2][2] = {};
	int i, j, k, dd1 = min(d1, d2), dd2 = max(d1, d2);
	queue<int> q1, q2;
	q1.push((d1)%n), q2.push(d1 == dd2);
	prev[(d1)%n][d1 == dd2][0] = -1;
	while(!q1.empty()) {
		i = q1.front(), q1.pop();
		j = q2.front(), q2.pop();
		k = (i*10+dd1)%n;
		if(prev[k][0][0] == 0) {
			prev[k][0][0] = i, prev[k][0][1] = j;
			q1.push(k), q2.push(0);
		}
		k = (i*10+dd2)%n;
		if(prev[k][1][0] == 0) {
			prev[k][1][0] = i, prev[k][1][1] = j;
			q1.push(k), q2.push(1);
		}
		if(prev[0][0][0] || prev[0][1][0])
			break;
	}
	if(prev[0][0][0] == 0 && prev[0][1][0] == 0)
		return -1;
	//printf("%d %d %d %d\n", prev[0][0][0], prev[0][1][0], d1, d2);
	//getchar();
	int cnt = 0, pi, pj, idx = 0;
	i = 0;
	if(prev[0][0][0])	j = 0;
	else				j = 1;
	while(i != -1) {
		buffer[idx++] = j ? dd2 : dd1;
		cnt++;
		pi = prev[i][j][0];
		pj = prev[i][j][1];
		i = pi;
		j = pj;
		//printf("%d %d %d\n", idx, i, j);
		//getchar();
	}
	return cnt;
}
int main() {
	int n; /*
	freopen("in.txt","r+t",stdin);
    freopen("out.txt","w+t",stdout);*/
	while(scanf("%d", &n) == 1 && n) {
		int i, j, k;
		int mnlen = 0xfffffff, mnIdx = -1;
		for(i = 1; i <= 9; i++) {
			int f = single(i, n);
			if(f == -1)	continue;
			if(f < mnlen)
				mnlen = f, mnIdx = i;
		}
		if(mnIdx != -1) {
			for(i = mnlen-1; i >= 0; i--)
				putchar(mnIdx+'0');
			puts("");
			continue;
		}
		for(i = 1; i <= 9; i++) {
			for(j = 0; j <= 9; j++) {
				if(i == j)	continue;
				int f = combine(i, j, n);
				if(f == -1)	continue;
				if(f < mnlen) {
					mnlen = f;
					for(k = 0; k < mnlen; k++)
						ret[k] = buffer[k];
				}
			}
		}
		for(i = mnlen-1; i >= 0; i--)
			putchar(ret[i]+'0');
		puts("");
	}
	return 0;
}