Available Areas

Time Limit : 8 sec, Memory Limit : 65536 KB

問題 4


 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

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。


Source: 5th Japanese Olympiad in Informatics, Trial Exam 2 , 2005-12-18
http://www.ioi-jp.org/