JUNGOL

You want to build a pair of positive integers. To do that, you are given a list of decimal digits to use. You must use every digit in the list exactly once, but you get to choose which ones to use for the first integer and which ones to use for the second integer. You also get to choose the order of the digits within each integer, except you cannot put a zero as the most significant (leftmost) digit in either integer. Note that you cannot choose just a zero for one integer either, because it would not be positive.

For example, you could be given the list [1, 0, 2, 0, 4, 3]. Two of the valid pairs you can build are (200, 143) and (3, 12400). The following pairs, on the other hand, are not valid:

(0102, 34): has a leading zero.
(0, 12340): has a non-positive integer.
(10, 243) and (12300, 47): the list of digits in each of these pairs is not exactly equal to the given list of digits.

Given the list of digits to use, what is the minimum absolute difference between the two built integers that can be achieved?

Input

The first line of the input gives the number of test cases, \mathbf{T}. \mathbf{T} lines follow. Each line describes a test case with a single string of digits \mathbf{D}. Each character of \mathbf{D} is a digit you must use.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum possible absolute difference between the two integers built from \mathbf{D} according to the rules above.

Example

Source

GCJ 2021r3 A

#10408

Build-A-Pair 5s 1024MB

Problems

Input

Output

Example

Source

#10408 upload 1 done 1 how_to_reg 1

Build-A-Pair timer 5s memory 1024MB

Problems translate English text_fields

Input

Output

Example

Source

Backlinks Official problem sets only

#10408

Build-A-Pair 5s 1024MB

Problems