Cover the Square

Oh no! The Enterprise is being attacked by a Borg unit cube. We all know that resistance is futile, but that won’t prevent the captain from trying anyway!

The engineers aboard the Enterprise have recently upgraded the size of the ships’s laser beam weapons, such that it can now cut large circular holes into enemy ships. In fact, they can even cut out holes of diameter one, which should get rid of most of the Borg cube in one deadly blow. However, the Borgs are frighteningly persistent, and the captain fears that the remaining undestroyed pieces will cause trouble. Thus, he wants to destroy at least n percent of the cube.

The Borg cube is positioned such that one of its faces is perpendicular to the enterprise’s line of sight, so the problem is approximately equivalent to trying to cover a unit square with circles of diameter one. Under this approximation and assuming that the undestroyed parts simply remain motionless at their original position, how many shots are required to destroy at least n percent of the cube?

The first line of the input will contain m, the number of test cases. m lines will follow, each containing an integer n between 0 and 100 inclusively.

For each test case, output the number of circles required to cover n percent of the square.

3
0
50
100

0
1
4

IPCP 2005 Northern Preliminary for Northeast North-America