I. Hail Pythagoras
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. You have to count the number of possible tuples $$$(a,b,c)$$$ such that $$$a \le b \le c$$$ and $$$a^2 + b^2 = c^2$$$ where $$$1 \le a \le n$$$.

Input

The first line contains the number $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases.

Each of the following $$$t$$$ lines contains one integer $$$n$$$ $$$(1 \le n \le 10^5)$$$.

Output

Print the number of possible tuples $$$(a,b,c)$$$ such that $$$a \le b \le c$$$ and $$$a^2 + b^2 = c^2$$$ where $$$1 \le a \le n$$$.

Example
Input
3
12
13
15
Output
11
12
16
Note

For test case 2, the expected tuples are listed below:

  • $$$(3, 4, 5)$$$
  • $$$(5, 12, 13)$$$
  • $$$(6, 8, 10)$$$
  • $$$(7, 24, 25)$$$
  • $$$(8, 15, 17)$$$
  • $$$(9, 12, 15)$$$
  • $$$(9, 40, 41)$$$
  • $$$(10, 24, 26)$$$
  • $$$(11, 60, 61)$$$
  • $$$(12, 16, 20)$$$
  • $$$(12, 35, 37)$$$
  • $$$(13, 84, 85)$$$