C - Yet Another Simple Math Problem Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

整数 N が与えられます。次の 2 条件をともに満たす正整数の組 (a, b) の個数を求めてください。

  • 1 \leq a, b \leq N
  • ある正整数の組 (x, y) が存在して、 x + y^2 = a と x^2 + y = b がともに成り立つ

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 10^{18}
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケース \mathrm{case}_i\ (1 \leq i \leq T) は以下の形式である。

N

出力

T 行出力せよ。 i 行目 (1 \leq i \leq T) には、 i 番目のテストケースの答えを出力せよ。

入力例 1

3
6
1
101

出力例 1

4
0
83

1 番目のテストケースでは、条件を満たす (a, b) の組は (a, b) = (2, 2), (3, 5), (5, 3), (6, 6) の 4 つです。
例えば、 (a, b) = (3, 5) に対しては、 (x, y) = (2, 1) とすれば x + y^2 = 3 = a 、 x^2 + y = 5 = b が成り立ち、条件が満たされます。

2 番目のテストケースでは、条件を満たす (a, b) の組は存在しません。