Cover the Square

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3115
64-bit integer IO format: %I64d      Java class name: Main

Description

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?

Input

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.

Output

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

Sample Input

3
0
50
100

Sample Output

0
1
4

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .