第5回日本情報オリンピック 模擬試験2

2005年12月18日
情報オリンピック日本委員会

問題

 IOI 不動産ではマンションの賃貸を行なっている. この会社が取り扱うマンションの部屋は 1LDK で, 下図のように面積が 2xy+x+y になっている. ただし, x, y は正整数である.

Figure_Madori

 IOI 不動産のカタログにはマンションの面積が昇順に(狭いものから順番に)書かれているが,この中にいくつか間違い(ありえない面積のもの)が混じっていることがわかった.

 カタログ(入力ファイル)は N+1 行で,最初の行に部屋数が書かれていて, 続く N 行に,1行に1部屋ずつ面積が昇順に書かれている. ただし, 部屋数は 100,000 以下, 面積は (2の31乗)-1 = 2,147,483,647 以下である. 5つの入力データのうち3つまでは, 部屋数 1000 以下,面積 30000 以下である.

 間違っている行数(ありえない部屋の数)を出力しなさい.

 出力ファイルにおいては, 出力の最後の行にも改行コードを入れること.


入力例
10
4
7
9
10
12
13
16
17
19
20
 
出力例
2