Oh no! The Rebel Alliance have found plans for a second Death Star – the deadliest weapon in the universe. It can destroy entire planets in a few seconds. If they allow it to be unleashed, it will mean a certain defeat.
The mission is clear – find Death Star and destroy it in a single big explosion. But now the Alliance needs to know how many explosives they need to prepare. And thus they need your help.
The Death Star can be represented as a perfect sphere with origin (0,0,0) and radius r. Rebel scientists have determined that to ensure its destruction, the Rebels must infiltrate it and place explosives at all points (x,y,z) inside the sphere such that x,y,z are integers, and the distance between (0,0,0) and (x,y,z) is also an integer.
Input specification
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consist of a single line containing a single integer r – the radius of the Death Star.
The largest test cases have r = 100 in the easy data set and r = 44444 in the hard data set.
Output specification
For each test case, output a single line containing a single integer – the number of explosives needed.
Example
In the first test case, the only explosive needs to be placed at the centre of the Death Star. In the second test case, additional explosives must be placed at positions (±1,0,0), (0,±1,0), (0,0,±1).