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 < k ≤ 1000, 0 ≤ ai < 263).

Output

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