eolymp
bolt
Try our new interface for solving problems
Problems

How many Fibonacci numbers

How many Fibonacci numbers

Time limit 1 second
Memory limit 128 MiB

Fibonacci sequence is a sequence where each element equals to the sum of two previous ones, except for the first two elements: F[1] = 1, F[2] = 1, F[n] = F[n-2] + F[n-1].

1 1 2 3 5 8 13 21 ...

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

Input data

The first line contains the amount k of input numbers. The next line contains k integers a[1], a[2], ..., a[k] (0 < k1000, 0a[i] < 2^63).

Output data

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

Examples

Input example #1
5
1 3 5 6 13
Output example #1
4