Mysterious number 6174

Problem code: HS086174

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 = 2088
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

---

Added by:	Jacek Dąbrowski
Date:	2009-02-13
Time limit:	1s-3s
Source limit:	50000B
Languages:	SED C99 strict C++ 4.0.0-8 C++ 4.3.2 TCL SCALA NEM PHP SCM guile LISP sbcl LISP clisp ERL TECS TEXT DOC PDF PS PERL 6 JS
Resource:	High School Programming League 2008/2009