Smallest Difference

Time limit1sMemory limit128 MB

Summary

Split the given distinct digits into two non-empty groups, order each into a number with no leading zero, and minimize the absolute difference.

Level: Medium7 of 10
Topics: Brute force, Backtracking, Math, Greedy
Solved: No attempts yet

Problem

You are given several distinct decimal digits. Choose a non-empty subset of these digits and arrange them in some order to form one integer. Arrange the remaining digits (which also form a non-empty set) in some order to form a second integer. Neither integer may begin with the digit 0, unless the integer is exactly 0.

For example, from the digits 0, 1, 2, 4, 6, and 7 you can form the pair of integers 10 and 2467. There are many such pairs: 210 and 764, 204 and 176, and so on. For the pair 204 and 176 the absolute difference is 28, and no pair formed under these rules achieves a smaller difference.

Find the smallest possible absolute difference between the two integers formed from the given digits.

Input

The first line contains the number of test cases. Each test case is given on one line containing at least two and at most ten decimal digits (0 through 9). No digit appears more than once on a line, and the digits are listed in increasing order, separated by exactly one space.

Output

For each test case, print on its own line the smallest absolute difference of the two integers that can be formed from the given digits under the rules above.

Examples2

Example 1
Input
```
1
0 1 2 4 6 7
```
Expected output
```
28
```
Example 2
Input
```
4
0 1
5 9
0 1 2
0 1 2 4 6 7
```
Expected output
```
1
4
8
28
```