Rabid Rabbit

유명한 마술사 피사의 레오나르도가 농장을 방문해 직원들에게 마술을 보여 줄 예정이다. 농장 마당의 한쪽 벽을 따라 토끼 우리가 길게 늘어서 있다. 각 우리에는 일정한 수의 토끼가 살고 있다. 마술사는 마술을 하려면 이 우리 줄을 사용해야 한다. 그런데 농장에서는 정비 작업을 계획하고 있어서, 연속된 구간 하나만 제공할 수 있다. 직원들은 레오나르도를 돕기 위해 구간 목록을 만들었다. 레오나르도는 목록에서 구간 하나를 고르고, 정비 중에는 그 구간 밖의 우리를 쓸 수 없다.

구간을 고르기 전에 레오나르도는 자신의 제약을 고려해야 한다. 매일 그는 고른 구간에서 마술을 한 번 한다. 마술에는 구간 안의 우리 두 개가 필요하며, 두 우리의 토끼 수 합이 양의 피보나치 수 중 하나와 같아야 한다. 양의 피보나치 수는 1과 2로 시작하는 무한 수열이며, 각 항은 바로 앞의 두 항의 합이다. 매일 사용하는 피보나치 수는 이전 날들에 사용한 모든 피보나치 수와 달라야 한다. 더 이상 마술을 할 수 없으면 레오나르도는 농장을 떠나야 한다.

목록의 각 구간에 대해, 레오나르도가 농장에 머물 수 있는 최대 일수를 구하시오.

첫 줄에 두 정수 $N$과 $Q$ ($1 \le N, Q \le 10^5$)가 주어진다. 이는 우리의 개수와 목록에 있는 구간의 개수이다. 둘째 줄에는 첫 번째 우리부터 순서대로 각 우리의 토끼 수 $A_0, A_1, \dots, A_{N-1}$ ($1 \le A_i \le 10^9$)이 공백으로 구분되어 주어진다. 이어지는 $Q$개의 줄에는 각각 구간의 첫 우리 번호 $P$와 마지막 우리 번호 $R$ ($0 \le P < R \le N-1$)이 주어진다. 우리는 $0$부터 $N-1$까지 번호가 매겨져 있다.

$Q$개의 줄을 출력한다. 각 줄에는 해당 구간에서 레오나르도가 농장에서 보낼 수 있는 최대 일수를 정수 하나로 출력한다.