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 without leading zeros.

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

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

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

What's the largest number that can be obtained?

Input

The first line contains a single integer t (1t104) — the number of testcases.

Each testcase consists of a single integer x (10x<10200000). x doesn't contain leading zeros.

The total length of the decimal representations of x over all testcases doesn't exceed 2105.

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.


Post a Comment

0 Comments