Description

Given a positive integer $d$, define

$$S_v=\{(x,y):x,y \in \mathbb{Z_{\ge 0}},x^2-dy^2=v\}$$

Compute:

$$\sum_{v=1}^{\lfloor\sqrt{d}\rfloor}v[S_v \neq \varnothing]$$

There are multiple queries.

Input Format

The first line contains a positive integer $t$, which indicates the number of queries.

The next $t$ lines each contain a positive integer $d$, representing one query.

Output Format

For each query, output one line containing one integer, which is the answer.

4
10
13
16
19

1
4
5
5

Hint

Sample Explanation

• For $d=10$, only $v=1$ satisfies $S_v \neq \varnothing$.
• For $d=13$, $v=1,3$ satisfy $S_v \neq \varnothing$.
• For $d=16$, $v=1,4$ satisfy $S_v \neq \varnothing$.
• For $d=19$, $v=1,4$ satisfy $S_v \neq \varnothing$.

Constraints

• For $30\%$ of the testdata, $t=1$, $1 \le d \le 70$.
• For $60\%$ of the testdata, $t=1$.
• For $100\%$ of the testdata, $1 \le t \le 4 \times 10^3$, $1 \le d \le 2 \times 10^6$.

---

Source: JROI-2 Summer Fun Round - T4.

Idea & Solution & Standard & Data: VinstaG173.

Retest: None.

Translated by ChatGPT 5