1483 - Laying of Tiles

時間制限 2 秒 / メモリ制限 256 MB / 得点 3 / Writer ei1903 / x 8 / 統計 /


TLE
2sec
MLE
256MB
得点
3

問題

正方形をこよなく愛する山本君ですが、残念ながら縦$ \ 1 \ \mathrm{cm} \ $横$ \ 2 \ \mathrm{cm} \ $の長方形のタイルしか持っていません。

そこで山本君はこのタイルを敷き詰めることで正方形を作り出すことにしました。

山本君は長方形のタイルを$ \ N \ $枚所持しています。
$N \ $枚以下のタイルを敷き詰めて作ることのできる正方形について、あり得る面積は何通りあるでしょうか?タイルは回転させてもよいです。

この問題では、$ \ T \ $個のテストケースが与えられるのでそのすべてに答えてください。

入力

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

$T$

一行目にテストケースの数$ \ T \ $が与えられ、その後$ \ T \ $行にわたって各テストケースが以下の形式で与えられる。

$N$

出力

$T \ $個のテストケースに対して答えを順に改行区切りで出力せよ。

制約

全ての入出力ケースについて以下を満たす。

  • $1 \leq T \leq 314$
  • $1 \leq N \leq 10^{18}$
  • 入力は全て整数

入出力例

入力例1

3
1
2
10

出力例1

0
1
2


入力例2

5
314
159
265
358
979

出力例2

12
8
11
13
22