High School Programming League Problems Archive

Jedną z czterocyfrowych liczb otacza magiczna aura. Jej moc przyciąga do siebie niemal wszystkie inne czterocyfrowe liczby.

Przypuśćmy że masz dowolną czterocyfrową liczbę, na przykład 4223. Stwórz dwie nowe liczby sortując jej cyfry malejąco oraz rosnąco: 4322 oraz 2234, i odejmij je od siebie. Jeśli będziesz powtarzać ten algorytm dla kolejnych wyników to w końcu niemal zawsze otrzymasz 6174!

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

Wejście

Pierwsza linia wejścia zawiera liczbę t, liczbę przypadków testowych. Kolejne t linii zawiera pojedynczą liczbę i, 1000 <= i <= 9999.

Wyjście

Dla każdego przypadku testowego wypisz liczbę kroków algorytmu potrzebnych do otrzymania magicznej liczby 6174. Jeśli dla podanej liczby nie da się otrzymać 6174 wypisz -1.

Przykład

Wejście:
5
6174
4223
2088
8532
1112
Wyjście:
0
3
2
1
5

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