Ravanan was the protagonist of Ramayanan.Agreed! But he was also the brightest man of that era. One of his special ingenuities was that he could arrange his troops in groups where the number of soldiers would be a perfect square for each group. For instance, if someone reported to Ravanan that the total army strength was 13, he would ask them to form two groups of 4 and 9 soldiers. In addition, he would always come up with the least number of groups that could be formed using perfect squares.
Laxman was aware of this capability of Ravanan and was eager to devise a program that could help him estimate the number of groups Ravanan would have formed given his total troop strength. Help Laxman achieve that.

INPUT:
an integer T (1 ≤ T ≤ 1000) : number of testcases
Each test case is represented by a number N(1 ≤ N ≤ 10000) which denotes the number of soldiers

OUTPUT:
For each test case, output the minimum number of groups that has to be formed such that those N soldiers are divided into groups of perfect square numbers.

SAMPLE INPUT
3
1
2
13

SAMPLE OUTPUT
1
2
2

Explanation

In the first test case, only one soldier, so only one group

In the second test case, two soldiers, so groups of 1 each

In the third test case, two groups : one of 4 soldiers and the other of 9 soldiers can be formed

见题面

见题面