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.
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