Many pieces of identification have a check digit, which is verified by performing operations on the other digits of the code, and comparing that result with the check digit.
You are bored, so you decided to experiment with this technology. Instead of a check digit, you have a number , and wanted to generate a sequence of single-digit, non-negative integers such that when the following operations are performed on the sequence, the result will equal
:
- Sum all the elements at odd indices in the sequence and square that result. We will call this value
.
- Sum all the elements at even indices in the sequence. We will call this value
.
- Sum
and
.
Note that the first element is at index .
Since this task was quite easy for you, you finished it and became bored again. The boredom quickly went away, however, after you asked yourself this question:
What is the length of the shortest sequence such that performing the operations on the sequence results in
?
Given cases for
, can you find the answer to your question for each case?
Constraints
Input Specification
The first line of input will contain an integer , the number of cases.
The next lines will each contain one integer
for that case.
Output Specification
Output lines. For each case, output a single integer, the length of the shortest sequence such that performing the operations on the sequence results in
.
Sample Input
2
19
120
Sample Output
2
6
Explanation for Sample Output
For , the shortest sequence is of length
:
4 3
as .
For , the shortest sequence is of length
:
1 8 6 7 3 5
as .
Note that this is not the only valid sequence, but it is of the shortest length.
Comments
I struggled on this question a bit, keep an eye out for rounding errors.
Thank you that helped me find the error.(even though I don't know why there is a rounding error in my code lol)