Problem Description

We have a stick with infinite length. Now we want to cut 3 sub-sticks with length x, y, z which is not large than L to form a right triangle. With unknown reasons we assume that x, y, z are all integers and satisfy that x, y, z are all co-primed each other. We want to know how many right triangles are there exist under our constraints

Input

The first line of input is an integer T (T<=5) indicating the number of test cases.
Each case contains a single integer L (L<=1,000,000,000,000).

Output

For each test case output a single integer in one line, indicating the number of right triangles.

1
5

1

Hint

In our test case, we could find a right triangle (3,4,5) which satisfy 3,4,5<=5 and gcd(3,4)=1,gcd(3,5)=1,gcd(4,5)=1.