Rabid Rabbit

Famous magician Leonardo from Pisa is about to visit the farm and amuse the staff with his tricks. A long row of rabbit hutches stands along one wall of the farm yard. Each hutch is permanently occupied by some number of rabbits. To perform his tricks, the magician needs to use the row of hutches. However, the farm is planning maintenance, and it can offer only one contiguous segment of the row. To help Leonardo, the staff compiled a list of segments. Leonardo chooses one segment from the list, and the hutches outside that segment are inaccessible to him during the maintenance.

Before Leonardo chooses a segment, he has to consider his own restrictions. Each day, he performs one trick on the chosen segment. A trick needs a pair of hutches in the segment such that the total number of rabbits in both hutches equals one of the positive Fibonacci numbers. The positive Fibonacci numbers form an infinite sequence that starts with 1 and 2, and each next term is the sum of the two terms before it. Each day, the Fibonacci number used must differ from all Fibonacci numbers used on previous days. When Leonardo cannot perform another trick, he must leave the farm.

For each segment in the list, determine the maximum number of days Leonardo can stay on the farm.

The first line contains two integers $N$ and $Q$ ($1 \le N, Q \le 10^5$), the number of hutches and the number of segments in the list. The second line contains $N$ space-separated integers $A_0, A_1, \dots, A_{N-1}$ ($1 \le A_i \le 10^9$), the number of rabbits in each hutch, starting from the first hutch. Each of the following $Q$ lines contains two integers $P$ and $R$ ($0 \le P < R \le N-1$), the number of the first and the last hutch in a segment. The hutches are numbered $0$ to $N-1$.

Output $Q$ lines. Each line contains one integer, the maximum number of days Leonardo can spend on the farm for the corresponding segment.