当前没有测试数据。

CF测试跳转：https://codeforces.com/contest/2241/problem/B

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.

Exammple

4
8
73
299
6767

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.