Marta collects banknotes and evaluates them by their serial numbers. A serial number is a positive integer, and Marta calls it beautiful if it is divisible by the sum of its digits in decimal notation. For example, is beautiful, because the sum of its digits equals 1 + 1 + 0 = 2 and 110 = 2 \cdot 55; the number is not beautiful, because is not divisible by 1 + 3 = 4.
Marta values beautiful pairs the most: two banknotes whose serial numbers are two consecutive beautiful integers and x + 1. For example, and form a beautiful pair, since is divisible by 1 + 1 + 1 = 3.
Marta is going to visit collectors. The -th collector has a bundle containing exactly one banknote for each serial number from m_i to 2m_i inclusive. For each collector, she wants to choose a beautiful pair in their bundle, that is, two consecutive beautiful integers and x + 1, for which
or determine that no such pair exists.
The first line contains a single integer (1 \le q \le 10^5) — the number of collectors.
Each of the following lines contains a single integer m_i (m_i \ge 1), written in decimal notation without leading zeros. The total number of digits across all m_i does not exceed 10^6 (\sum |m_i| \le 10^6).
Output lines, the -th of which is the answer for the -th collector.
If there is a beautiful pair (x, x+1) in the -th collector's bundle, output the number in decimal notation without leading zeros. If there are multiple possible answers, output any of them.
If there is no beautiful pair in the bundle, output a single number .
Example 1
The first collector has the banknotes and in their bundle; both numbers are beautiful, so they form the only possible beautiful pair.
The second collector's serial numbers are 8, 9, \ldots, 16. Among them, the beautiful ones are , , and , so there are exactly two possible beautiful pairs: the pairs and .
The third collector's serial numbers are 30, 31, \ldots, 60; no two consecutive numbers among them are both beautiful.
For the fourth collector, one of the possible answers is 2754 = 18 \cdot 153 and 2755 = 19 \cdot 145, where and are their digit sums.
For the fifth collector, the digit sums of and equal and , and it holds that 987654321987655230 = 90 \cdot 10973936910973947 and 987654321987655231 = 91 \cdot 10853344197666541.