# Internet Problem Solving Contest

## Problem A – A+B

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

### Problem specification

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 specification

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.

In the easy subproblem A1 we have t = 900 and each test case consists of exactly 3 digits.

In the hard subproblem A2 we have t = 1000 and the number of digits in each test case is between 2 and 16, inclusive.

### Output specification

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

### Example

Input:

``````4

001

175

21

444444``````

Output:

``````10
76
3
44448``````

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 example test case: 10+0, 71+5, 1+2, and 44444+4.