Cake

Wheatley is at the best party in the world: it has infinitely many cakes! Each cake is a square with an integer side length (in cm). The party has infinitely many cakes of every possible integer side length. The cakes all have the same depth, so we only consider their areas.

Wheatley is determined to eat one or more cakes whose total combined area is exactly N cm2. But since he is health-conscious, he wants to eat as few cakes as possible. Can you help him calculate the minimum number of cakes he can eat?

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

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of cakes that Wheatley can eat while eating the exact total area N.

In sample case 1, the only possible strategy is for Wheatley to eat three cakes of side length 1.

In sample case 2, Wheatley can eat one cake of side length 2, which requires fewer cakes than eating four cakes of side length 1.

In sample case 3, the best strategy is for Wheatley to eat one cake of side length 2 and one cake of side length 1.