Настя любить математику 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