6174

In 1949 the Indian mathematician Kaprekar devised the Kaprekar operation. It applies to any four-digit number whose digits are not all identical (numbers like 1111 or 2222 are excluded) and repeats the following steps:

1. Rearrange the digits to form the largest possible number and the smallest possible number.
2. Subtract the smallest from the largest.
3. Treat the difference as the new four-digit number and repeat.

Whenever an intermediate value has fewer than four digits, pad it on the left with zeros so it is always handled as a four-digit number.

The operation is simple, yet Kaprekar found a remarkable fact. Take 2008 as an example. The largest number made from its digits is 8200 and the smallest is 0028.

• 8200 - 0028 = 8172
• 8721 - 1278 = 7443
• 7443 - 3447 = 3996
• 9963 - 3699 = 6264
• 6642 - 2466 = 4176
• 7641 - 1467 = 6174

Once 6174 is reached, every further step produces 6174 again. This is not special to 2008: every four-digit number that is not made of a single repeated digit reaches 6174 by repeating the Kaprekar operation. For 2008 it took 6 steps.

Given a four-digit number, write a program that determines how many steps of the Kaprekar operation are needed to reach 6174. If the number is already 6174, output 0.

Input is given on standard input. The first line contains the number of test cases $T$ ($1 \le T \le 20$). Each of the next $T$ lines contains one four-digit number between 1000 and 9999. No number consists of a single repeated digit (such as 1111 or 2222).

For each test case, print on its own line the number of Kaprekar steps required for the given number to reach 6174.