Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

Now a days, Roy is chilling with his friend. But suddenly, He gets an idea to create a problem. Problem is very simple,
You are given an integer X, You need to find out minimum numbers of perfect square numbers sum of which is exactly X.
But here is a condition ,

• You can not use same perfect square numbers more than once.

Some perfect square numbers: 1 , 4, 9, 16, 25, 36...

Input

First Line T, number of test cases.
In each test case, an integer X.

\(1 <= T <= 10^5\)
\(1 <= X <= 2 * 10^5\)

Output

If the answer exist, print the minimum numbers of perfect square need to make equal X, otherwise print -1.

Sample

2
10
11

2
-1

Sample test case explaintation:
First Test case, X = 10;
If we choose {1,9}, their sum = 1 + 9 = 10 equal to X.
So minimum perfect square need 2. Answer is 2.

Second Test case, X = 11;
Only one way we can make,if we choose {1,1,9}, their sum = 1 + 1 + 9 = 11 equal to X.
But we can't choose same perfect numbers more than once. So answer is -1.