Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

strings

*1100

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Minor Reduction

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

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

The total length of the decimal representations of $$$x$$$ over all testcases doesn't exceed $$$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

21005790

Output

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/04/2024 17:36:00 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|