B. Minor Reduction Solution | Educational Codeforces Round 121 (Rated for Div. 2)

 B. Minor Reduction

You are given a decimal representation of an integer x$x$ without leading zeros.

You have to perform the following reduction on it exactly once: take two neighboring digits in x$x$ and replace them with their sum without leading zeros (if the sum is 0$0$, it's represented as a single 0$0$).

For example, if x=10057$x=10057$, the possible reductions are:

• choose the first and the second digits 1$1$ and 0$0$, replace them with 1+0=1$1+0=1$; the result is 1057$1057$;
• choose the second and the third digits 0$0$ and 0$0$, replace them with 0+0=0$0+0=0$; the result is also 1057$1057$;
• choose the third and the fourth digits 0$0$ and 5$5$, replace them with 0+5=5$0+5=5$; the result is still 1057$1057$;
• choose the fourth and the fifth digits 5$5$ and 7$7$, replace them with 5+7=12$5+7=12$; the result is 10012$10012$.

What's the largest number that can be obtained?

Input

The first line contains a single integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of testcases.

Each testcase consists of a single integer x$x$ (10≤x<10200000$10\le x<{10}^{200000}$). x$x$ doesn't contain leading zeros.

The total length of the decimal representations of x$x$ over all testcases doesn't exceed 2⋅105$2\cdot {10}^5$.

Output

For each testcase, print a single integer — the largest number that can be obtained after the reduction is applied exactly once. The number should not contain leading zeros.

Example

input

Copy

2
10057
90

output

Copy

10012
9

Note

The first testcase of the example is already explained in the statement.

In the second testcase, there is only one possible reduction: the first and the second digits.