Ruby plays a game as advised by her sister Emerald. The game is as follows: First, she picks a number N. Then she starts picking 2N, 3N, 4N and so on. Whenever she picks a number, she keeps notes down all the digits number. She keeps track of which digits (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) she has seen at least once so far. Once she has seen each of the ten digits at least once, she would win the game.
Ruby must start with N and must always name (i + 1) × N directly after i × N. For example, suppose Ruby picks N = 10. She would count as follows:
N = 10. Now she has seen the digits 0, and 1.
2N = 20. Now she has seen the digits 0, 1, and 2.
3N = 30. Now she has seen the digits 0, 1, 2, and 3.
4N = 40. Now she has seen the digits 0, 1, 2, 3, and 4.
5N = 50. Now she has seen the digits 0, 1, 2, 3, 4, and 5.
6N = 60. Now she has seen the digits 0, 1, 2, 3, 4, 5, and 6.
7N = 70. Now she has seen the digits 0, 1, 2, 3, 4, 5, 6, and 7.
8N = 80. Now she has seen the digits 0, 1, 2, 3, 4, 5, 6, 7, and 8.
9N = 90. Now she has seen all ten digits she wins.
So, the last number which she saw is 90 so the answer is 90.
What is the last number that she will pick before she wins? If she will not win at all, print LOSE instead.

Input

The first line of the input gives the number of test cases, T.
T test cases follow.
Each consists of one line with a single integer N, the number Ruby has chosen.

Output

For each test case, output one line containing the last number that Ruby will pick before winning or LOSE if it is not possible, according to the rules described in the statement.

Constraints

• 1 ≤ T ≤ 100
• 0 ≤ N ≤ 1000000