7404：Cakes

There is a party in the Shanghai Polytechnic University. There are infinitely many cakes each student can have. Each cake is a square with an integer side length (in cm). There are infinitely many cakes of every possible integer side length in the party and cakes all have the same depth, so it’s enough of you to only consider the areas.
You are intended to eat one or more cakes that have a total combined area of exactly N cm2. But, due to your health-conscious, you need to eat as few cakes as possible. Please calculate the minimum number of cakes you can eat.

The input starts with one line containing one integer T, which is the number of test cases. T test cases follow. Each case consists of one line with one integer N, which is the exact total cake area that you want to eat.

For each test case, output one line containing Case #t: ans, where t is the test case number and ans is the minimum number of cakes that you can eat. Be sure that the exact total area is N.

1 ≤ T ≤ 100 1 ≤ N ≤ 10000