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.