e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

How many Fibonacci numbers

How many Fibonacci numbers

Fibonacci sequence is a sequence where each element equals to the sum of two previous ones, except for the first two elements: F1 = 1, F2 = 1, Fn = Fn-2 + Fn-1.

1 1 2 3 5 8 13 21 ...

Given array of integers. How many Fibonacci numbers are there?

Input

The first line contains the amount k of input numbers. The next line contains k integers a1, a2, ..., ak (0 < k1000, 0ai < 263).

Output

Print a single number - how many Fibonacci numbers in the given array of integers.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5
1 3 5 6 13
Output example #1
4