time limit per test

2 seconds

memory limit per test

256 megabytes

We call a positive integer number fair if it is divisible by each of its nonzero digits. For example, 102 is fair (because it is divisible by 1 and 2), but 282 is not, because it isn't divisible by 8. Given a positive integer n. Find the minimum integer x, such that n≤x and x is fair.

Input

The first line contains number of test cases t (1≤t≤103). Each of the next t lines contains an integer n (1≤n≤1018).

Output

For each of t test cases print a single integer — the least fair number, which is not less than n.

Example

Input

Copy

4
1
282
1234567890
1000000000000000000

Output

Copy

1
288
1234568040
1000000000000000000

Note

Explanations for some test cases:

• In the first test case number 1 is fair itself.
• In the second test case number 288 is fair (it's divisible by both 2 and 8). None of the numbers from [282,287] is fair, because, for example, none of them is divisible by 8.

解题说明：此题是一道数学题，直接从 n开始逐个递增检查，直到找到第一个满足条件的数即可。针对每个数字，判断其中的每一位，如果为0就跳过，否则进行整除判断。

#include<stdio.h>
int main()
{
	int t;
	long long int a, k;
	scanf("%d", &t);
	while (t) 
	{
		scanf("%lld", &a);
		k = a;
		while (k != 0)
		{
			if (k % 10 == 0)
			{
				k = k / 10;
			}
			else
			{
				if (a % (k % 10) == 0)
				{
					k = k / 10;
				}
				else 
				{
					a++; 
					k = a;
				}
			}
		}
		printf("%lld\n", a);
		t--;
	}
	return 0;
}