B. Good times Good times

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

An integer n is said to be good if it contains at most two distinct digits in its decimal representation. For example, the integers 3, 8588, 67 are good, whereas the integers 123, 9447 are not.

You are given an integer x (1 \le x \lt 10^8), which is good. Your task is to find an integer y (2 \le y \le 10^9) such that both of the following conditions are satisfied:

• y is good.
• x \times y is good.

Input

The first line contains an integer t (1 \le t \le 10^4) — the number of test cases. The description of each test case follows.

Each test case contains a single integer x (1 \le x \lt 10^8). It is guaranteed that x is good.

Output

For each test case, print a single integer y (2 \le y \le 10^9) such that both the integers y and x \times y are good.

If there are multiple valid answers, output any one of them.

Example

Input

4
8
73
299
6767

Output

11
4
26
3366

Note

For the first test case, we have x = 8; choosing y = 11 is valid because both y = 11 and x \times y = 88 are good.

For the second test case, we have x = 73; choosing y = 4 is valid because both y = 4 and x \times y = 292 are good.