The greatest western mathematician of the middle age Leonardo Pisano Bigollo was nothing less than a wizard. Among his many contributions, the most important one is Libre Abaci. This book introduced the hindu-arabic numerals to the world, and created the system that is used in the world till date. Without him, we might have been stuck with roman numerals for ages. Sadly, today he is remembered primarily for one thing and one thing only, the Fibonacci sequence. You are a historian and want to pay homage to Fibonacci's legacy. Given an array of size n, you decide to count the no. of distinct Fibonacci numbers in the array. We consider fibonacci numbers to start from 1.

Input

The first line contains the value of n.
The next line contains n space separated integers, where the ith integer is A[i].

Output

Print a single line containing the number of distinct Fibonacci numbers in the array.

Constraints

1 ≤ n ≤ 100000
1 ≤ A[i] ≤ 10¹⁸