## IPSC 2015

## 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.

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.*