A+B

Interview

Time limit1sMemory limit1024 MB

Summary

Rearrange the given digits into two numbers without leading zeros so that their sum is as large as possible, and print that sum.

Level: Medium5 of 10
Topics: Greedy, Sorting, String
Solved: No attempts yet

Problem

Our first problem today is as easy as $a$ + $b$ .

You are given a string of digits. Rearrange those digits to build two nonnegative integers $a$ and $b$ such that the sum $a + b$ is as large as possible.

Each number must consist of at least one digit. Leading zeros are not allowed, but the number zero consisting of a single digit 0 is allowed. You have to use each digit exactly as many times as it occurs in the given input string.

Input

The first line of the input file contains an integer $t$ specifying the number of test cases. Each test case is preceded by a blank line. Each test case consists of a single line containing one string of digits. If there are more than 2 digits in the string, not all of them are zeros.

Output

For each test case, output a single line with a single integer: the largest sum that can be achieved.

Hint

The first two test cases could appear in the easy input file a1.in, the other two could only appear in the hard input file a2.in.

One optimal arrangement of digits for each test case is 10+0, 71+5, 1+2, and 44444+4.

Examples1

Example 1
Input
```
4

001

175

21

444444
```
Expected output
```
10
76
3
44448
```