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\)