Apartment Rental

Time limit1sMemory limit256 MB

Summary

Count how many given numbers up to 2^31-1 cannot be written as 2xy + x + y with positive integers x and y.

Level: Medium7 of 10
Topics: Number theory, Math, Binary search, Sorting
Solved: No attempts yet

Problem

Donggyu Real Estate rents out apartments. The area of an apartment's room is given by $2xy + x + y$ , where $x$ and $y$ are positive integers.

The Donggyu Real Estate catalog lists apartment areas in ascending order. However, some of these values are impossible sizes that cannot be produced by the formula above. If you say you want to rent an apartment of such a size, Donggyu shouts "Wrong!" and walks off with only the commission.

Given the apartment areas written in the catalog, write a program that counts how many of them are impossible sizes.

Input

The first line contains the number of apartment areas $N$ . Each of the next $N$ lines contains one area, in the order listed in the catalog.

$N$ is at most $100{,}000$ , and each area is a positive integer at most $2^{31}-1$ .

Output

Print the number of impossible apartment areas on the first line.

Examples3

Example 1
Input
```
10
4
7
9
10
12
13
16
17
19
20
```
Expected output
```
2
```
Example 2
Input
```
1
4
```
Expected output
```
0
```
Example 3
Input
```
1
9
```
Expected output
```
1
```