Palindrome Addition Transformation

You are given a positive integer for each test case. Your task is to repeatedly add the number and its reverse until the result becomes a palindrome. A number is a palindrome if it reads the same forward and backward. Formally, for a number \( n \), let \( R(n) \) be the number obtained by reversing the digits of \( n \). You need to compute the minimum number of additions required such that:

\( n + R(n) \) becomes a palindrome.

If the process does not result in a palindrome within 1000 additions, output \(-1\) for that test case.

Note: The reverse of a number is obtained by reading its digits from right to left. For example, the reverse of 56 is 65, and 56 + 65 = 121 which is a palindrome.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \( T \) representing the number of test cases. Each of the next \( T \) lines contains a single positive integer.

For example:

3
87
77
349

outputFormat

For each test case, output on a separate line the minimum number of additions needed to obtain a palindrome. If it is not possible to obtain a palindrome within 1000 additions, output -1.

For the sample input above, the output would be:

4
0
3

## sample

1
56

1

</p>