Monasm has a very funny number called "A very odd number"!!!

An integer is "a very odd number" when both of these hold: the number itself is odd, and every digit that appears in it appears an odd number of times (each distinct digit shows up 1, 3, 5, ... times, never an even number of times). For example, 3, 111 and 1211 are very odd (1211 is odd, and the digit 1 appears 3 times while 2 appears once), but 34 is not (it is even), 22 is not (it is even and has 2 twice), and 121 is not (the digit 1 appears twice).

And there is an even funnier one — "A very very odd number": it is everything a very odd number is, but on top of that every digit must itself be odd. For example, 13, 111 and 13579 are very very odd, but 123 is not (the digit 2 is even).

Given a very very odd number A (1 ≤ A ≤ 10⁸), your task is to find a value of B such that both of these conditions are followed:

• B is a very odd number.
• A × B is a very odd number.

Input

The first line contains an integer T (1 ≤ T ≤ 1000) — the number of test cases. Each of the next T lines contains a very very odd number A (Get it?? A very very odd number A).

Output

For each test case, print a single integer B (Btw 2 ≤ B lmao) on its own line satisfying the conditions above. If several answers exist, print any of them.

Example

3
3
13
135

5
19
31

For the second case, B = 19 is very odd(it is odd, with 1 and 9 appearing once), and A × B = 13 × 19 = 247 is very odd too (odd, with 2, 4 and 7 each appearing once).