High School Programming League Problems Archive

There is a strange aura surrounding one of the four digit numbers. Its power seems to draw almost all other numbers to it.

Suppose you have a four digit number, for example 4223. Create two new numbers by sorting its digits in descending and ascending order: 4322 and 2234, and subtract them. If you apply this procedure to the result you will almost always reach 6174!

4332 - 2334 = 1998
9981 - 1899 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174
7641 - 1467 = 6174
...

Input

The first line of input will contain t, the number of test cases. Then t lines with a single integer i, 1000 <= i <= 9999.

Output

For each test case output the number of steps it takes to reach the mysterious number 6174. If 6174 cannot be reached, output -1.

Example

Input:
5
6174
4223
2088
8532
1112
Output:
0
3
2
1
5