Назовём натуральное число справедливым, если оно делится на каждую из своих ненулевых цифр. Например, число \(102\) справедливое (так как оно делится и на \(1\), и на \(2\)), а число \(282\) — нет, потому что не делится на \(8\). По данному \(n\) найдите минимальное \(x\), такое что \(n \leq x\) и \(x\) — справедливое.
В первой строке содержится \(t\) — количество тестовых случаев (\(1 \leq t \leq 10^3\)). В каждой из следующих \(t\) строк по одному целому числу \(n\) (\(1 \leq n \leq 10^{18}\)).
Для каждого из \(t\) тестовых случаев в новой строке выведите наименьшее справедливое число, не меньшее \(n\).
Пояснения к некоторым тестовым случаям:
4 1 282 1234567890 1000000000000000000
1 288 1234568040 1000000000000000000
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач