Internet Problem Solving Contest

• Easy input data set – A1
• Hard input data set – A2

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.