E - R-Connected Components Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

正整数 R に対し、以下の無限無向グラフの連結成分数を f(R) と定義します。

  • 頂点集合は \mathbb Z^2 である。すなわち、任意の 2 つの整数 x, y に対し、頂点 (x, y) が存在する。
  • 頂点 (x_1, y_1) と頂点 (x_2, y_2) の間には、|x_1 - x_2|^2 + |y_1 - y_2|^2 = R であるとき、かつそのときに限り辺が存在する。

正整数 R が与えられるので、f(R) を出力してください。ただし、f(R) が有限でないときは、inf を出力してください。

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

制約

  • 1 \le T \le 100
  • 1 \le R \le 10^9
  • 入力はすべて整数

部分点

  • 追加の制約 R \le 10^3 を満たすデータセットに正解した場合は 25 点が与えられる。

入力

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

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

\mathrm{case}_i は i 個目のテストケースを表す。各テストケースは以下の形式で与えられる。

R

出力

各テストケースについて、f(R) が有限ならば f(R) を、f(R) が有限でないならば inf を出力せよ。

入力例 1

3
1
2
3

出力例 1

1
2
inf

1 個目のテストケースでは、R=1 です。以下のように辺が張られるので、連結成分の個数は 1 個です。

2 個目のテストケースでは、R=2 です。以下のように辺が張られるので、連結成分の個数は 2 個です。

3 個目のテストケースでは、R=3 です。このグラフには辺がなく、連結成分の個数は有限ではありません。