Fair Numbers

2000ms

262144K

Description:

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 \leq x$$$ and $$$x$$$ is fair.

Input:

The first line contains number of test cases $$$t$$$ ($$$1 \leq t \leq 10^3$$$). Each of the next $$$t$$$ lines contains an integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$).

Output:

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

Sample Input:

4
1
282
1234567890
1000000000000000000

Sample Output:

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$$$.

Informação

Provedor Codeforces

Código CF1411B