Project Euler #195: Inscribed circles of triangles with one angle of 60 degrees

_{This problem is a programming version of Problem 195 from projecteuler.net}

Let's call an integer sided triangle with exactly one angle of degrees a -degree triangle.

Let be the radius of the inscribed circle of such a -degree triangle.

There are -degree triangles for which .

Let be the number of -degree triangles for which , so , , and .

Find for some .

Input Format

First line of each test file contains a single integer which is the number of queries in the file. lines follow with a single integer on each.

Constraints

Output Format

Output exactly lines with a single integer on each. The integer of the -th line should be the answer for the query with as an input.

Sample Input 0

Sample Output 0

1234
22767
359912