Nonnegative Pell Equation Sum

Given a positive integer (d), define the set [ S_v = { (x,y) : x,y \in \mathbb{Z}{\ge 0},; x^2 - d,y^2 = v }, ] for any positive integer (v). For each query, you are required to compute [ \sum{v=1}^{\lfloor\sqrt{d}\rfloor} v,[S_v \neq \varnothing], ] where ([S_v \neq \varnothing]) is 1 if (S_v) is non-empty and 0 otherwise.

You are given multiple queries. For each query, output the corresponding sum on a new line.

Note: All formulas are in (\LaTeX) format. For instance, the set definition and summation above are given in proper (\LaTeX) style.

inputFormat

The first line of input contains a positive integer (T) denoting the number of queries. Each of the next (T) lines contains a single positive integer (d).

outputFormat

For each query, output a single line containing the computed sum [ \sum_{v=1}^{\lfloor\sqrt{d}\rfloor} v,[S_v \neq \varnothing]. ]

sample

1
4

1