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.
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.
For each test case, output a single line with a single integer: the largest sum that can be achieved.
4 001 175 21 444444
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
One optimal arrangement of digits for each example test case: 10+0, 71+5, 1+2, and 44444+4.