Настя любить математику i твердо знає, що рахувати овець перед сном тупо та неефективно. Алгоритм Настi для засипання дає 100-вiдсоткову гарантiю заснути!

Спочатку Настя вибирає цiле число N . Потiм вона починає називати числа ~N~ , ~2 × N~ , ~3 × N~ i т.д. Щоразу, коли вона називає чергове число, вона звертає увагу на цифри в цьому числi. Настя вiдслiдковує, якi цифри (0, 1, 2, 3, 4, 5, 6, 7, 8 i 9) вона бачила хоча б один раз, як частину числа, яке вона називала. Як тiльки вона побачить кожну цифру хоча би один раз, то зразу ж засне. Настя починає з ~N~ i завжди повинна називати ~(i + 1) × N~ зразу пiсля ~i × N~ .

Наприклад, припустимо, що вона починає з ~N~ = 1692. Послiдовнiсть Настi буде мати вигляд:

~N = 1692~ - Настя побачила цифри 1, 2, 6 i 9.

~2 × N = 3384~ - вона побачила цифри 1, 2, 3, 4, 6, 8 i 9.

~3 × N = 5076~ - тепер вона побачила всi десять цифр i засинає.

Напишiть програму, яка визначить останнє число, яке назве Настя перед сном?

Формат вхідних даних

Перший рядок мiстить ~T~ ~(1 \le T \le 100)~ кiлькiсть тестiв.

Кожен тест складається з одного рядка i мiстить єдине цiле число ~N~ ~(0 \le N \le 10^6)~.

Формат вихідних даних

Для кожного тесту в окремому рядку вивести останнє число, яке назве Настя перед сном. Якщо вона буде рахувати вiчно, то слiд вивести INSOMNIA.

Приклад вхідних даних

5
0
1
2
11
1692

Приклад вихідних даних

INSOMNIA
10
90
110
5076