How many Fibonacci numbers#1358

How many Fibonacci numbers

1 second

128 megabytes

Medium

The Fibonacci sequence is defined as follows:

F_{1} = 1, F_{2} = 1, F_{n} = F_{n - 2} + F_{n - 1}, n \geq 3

F_1 = 1, \\ F_2 = 1, \\ F_n = F_{n - 2} + F_{n - 1}, n \ge 3

The first elements of the sequence are:

1, 1, 2, 3, 5, 8, 13, 21, ...

1, 1, 2, 3, 5, 8, 13, 21, ...

An array of integers is given. Determine how many elements of this array are Fibonacci numbers.

Input

The first line contains the number of elements in the array $k$ . The second line contains $k$ integers $a_{1}, a_{2}, \dots, a_{k} (0 < k \leq 1000, 0 \leq a_{i} < 2^{63})$ a_1, a_2, \dots, a_k~(0 < k \le 1000, 0 \le a_i < 2^{63}).

Output

Print the number of elements in the array that are Fibonacci numbers.

Examples

Example 1

Loading

F_{1} = 1, F_{2} = 1, F_{n} = F_{n - 2} + F_{n - 1}, n \geq 3

1, 1, 2, 3, 5, 8, 13, 21, ...

a_{1}, a_{2}, \dots, a_{k} (0 < k \leq 1000, 0 \leq a_{i} < 2^{63})