Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8821

Jo'natishlar soni: 714441

Muhokama yozuvlari: 4541

Yangiliklar soni: 97

Yangiliklar izohlari: 1174


So'ngi izohlar

751. Count Fibonacci numbers
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

Fibonacci sequence - it's a sequence in which each element is equal to the sum of the two previous ones, except for the first two elements of F1 = 1, F2 = 1, Fn = Fn-2 + Fn-1.

1 1 2 3 5 8 13 21

   Given an array of integers, of which perhaps is the Fibonacci numbers. Count the Fibonacci numbers in a given set of numbers.

Input

The first line contains the number k - the number of numbers in the next line contains k integers a1,a2, , ak (0 < k  105, 1  ai < 263).

Output

 Print a single number - the count of Fibonacci numbers.

Samples

Input

Output

1

5

1 3 5 6 13

4

s

Tayyorladi: Azat Yusupov
Text from: e-olimp.com
Mening urinishlarim(0) Muhokama (2) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(55) Barcha urinishlar(190)