H. Pythagoras' Playhouse
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Little Pythagoras has a semicircular playhouse of radius $$$r$$$, where he loves to play with triangular toys. But he's very picky about his toys — he only plays with special ones he calls Pythagorean triangles.

A Pythagorean triangle is a non-degenerate triangle that has one right angle and all three of its side lengths are integers.

Today, Pythagoras is visiting the fair, which has toys of all possible shapes and sizes. Pythagoras wants to buy every Pythagorean triangle from the fair that can somehow fit entirely inside his playhouse.

Your task is to count the number of toys that Pythagoras will buy, i.e., the number of different Pythagorean triangles that can somehow fit inside his playhouse (one triangle at a time).

Two triangles are considered the same if their three side lengths are the same when sorted in non-decreasing order. For example, triangles with sides $$$(3,4,5)$$$ and $$$(5,3,4)$$$ are considered the same because their sorted side lengths are the same, i.e., $$$(3,4,5)$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

Each test case consists of a single line containing a single integer $$$r$$$ ($$$1 \le r \le 10^7$$$) — the radius of the playhouse.

It is guaranteed that the sum of $$$r$$$ over all test cases does not exceed $$$10^7$$$.

Output

For each test case, output a single integer in a line — the number of toys that Pythagoras will buy from the fair today.

Example
Input
5
4
8
10
50
260
Output
1
4
6
52
406
Note

For every right-angled triangle with side lengths $$$(a, b, c)$$$ where $$$c$$$ is the length of the hypotenuse, $$$a^2 + b^2 = c^2$$$. The converse is also true, i.e., for a triangle with side lengths $$$(a, b, c)$$$, if $$$a^2 + b^2 = c^2$$$, then the triangle is a right-angled triangle where $$$c$$$ denotes the length of the hypotenuse.

For example:

  • A triangle with side lengths $$$(3, 4, 5)$$$ is a Pythagorean triangle.
  • A triangle with side lengths $$$(3, 3, 3)$$$ is not — it has no right angle.
  • A triangle with side lengths $$$(1, 1, \sqrt{2})$$$ is not — even though it has a right angle, one of the sides is not an integer.

Although $$$(5, 12, 13)$$$ and $$$(6, 8, 10)$$$ are valid Pythagorean triangles, it can be proven that neither of them can fit inside a semicircle of radius $$$4$$$ in any orientation.

For the first test case, the only Pythagorean triangle that fits inside the playhouse has sorted side lengths $$$(3, 4, 5)$$$.

Two examples from the first two test cases are illustrated in the following diagram: