Назовём натуральное число справедливым, если оно делится на каждую из своих ненулевых цифр. Например, число \(102\) справедливое (так как оно делится и на \(1\), и на \(2\)), а число \(282\) — нет, потому что не делится на \(8\). По данному \(n\) найдите минимальное \(x\), такое что \(n \leq x\) и \(x\) — справедливое.
Выходные данные
Для каждого из \(t\) тестовых случаев в новой строке выведите наименьшее справедливое число, не меньшее \(n\).
Примечание
Пояснения к некоторым тестовым случаям:
- В первом тестовом случае число \(1\) само по себе является справедливым.
- Во втором тестовом случае число \(288\) — справедливое (делится и на \(2\), и на \(8\)). Ни одно число из отрезка \([282, 287]\) не является справедливым, потому что, например, не делится на \(8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
282
1234567890
1000000000000000000
|
1
288
1234568040
1000000000000000000
|