Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS086174 - Mysterious number 6174

{if $locale=="pl"}{literal}

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
{/literal}{else}{literal}

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
{/literal}{/if}

Added by:Jacek Dąbrowski
Date:2009-02-13
Time limit:1s-4.125s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:High School Programming League 2008/2009

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.