A number is known as special bit number if its binary representation contains atleast two consecutive 1's or set bits. For example $7$ with binary representation $111$ is a special bit number. Similarly $3$ $(11)$ is also a special bit number as it contains atleast two consecutive set bits or ones.

Now the problem is, You are given an Array of $N$ integers and $Q$ queries. Each query is defined by two integers $L$, $R$. You have to output the count of special bit numbers in the range $L$ to $R$.

Input

Contains integer $N$, no of Array elements and $Q$ - Total Number of Queries.

Next line contains $N$ integers $A[i]$ defining Array elements.

Next $Q$ lines contains Queries of the type $1 \le L \le R \le N$

Output

Output  $Q$ lines containing answer for the ith Query.

Constraints

$0 \le A[i] \le 10^9$

$1 \le N \le 10^5$

$1 \le Q \le 10^5$