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 ~N~, 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 ~N~:

• Sum all the elements at odd indices in the sequence and square that result. We will call this value ~x~.
• Sum all the elements at even indices in the sequence. We will call this value ~y~.
• Sum ~x~ and ~y~.

Note that the first element is at index ~1~.

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 ~N~?

Given ~T~ cases for ~N~, can you find the answer to your question for each case?

Constraints

~1 \le T \le 10^5~

~1 \le N \le 10^{18}~

Input Specification

The first line of input will contain an integer ~T~, the number of cases.

The next ~T~ lines will each contain one integer ~N~ for that case.

Output Specification

Output ~T~ lines. For each case, output a single integer, the length of the shortest sequence such that performing the operations on the sequence results in ~N~.

Sample Input

2
19
120

Sample Output

2
6

Explanation for Sample Output

For ~N = 19~, the shortest sequence is of length ~2~:

4 3

as ~4^2 + 3 = 19~.

For ~N = 120~, the shortest sequence is of length ~6~:

1 8 6 7 3 5

as ~(1 + 6 + 3)^2 + 8 + 7 + 5 = 120~.

Note that this is not the only valid sequence, but it is of the shortest length.