B. Two Squares
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

You are given an non-negative integer $$$n$$$.

Your task is to find the the count of $$$x$$$ $$$(0 \le x \le n)$$$ that can be showed that $$$x = a^2 + b^2$$$ ($$$a$$$ and $$$b$$$ are integers).

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases.

The each test case contains a single integer $$$n$$$ $$$(0 \le n \le 10^7)$$$.

Output

For each test case, output a single integer.

Example
Input
4
1
6
576
10000000
Output
2
5
200
1985460
Note

In the second test case, it can be proven that $$$3$$$ and $$$6$$$ can not be showed that $$$a^2 + b^2$$$.