Weird Decimal XOR

The decimal digits $0,1,\cdots,9$ are divided into five colors and two states as follows.

The five colors are placed on a cycle in the following order.

Define the composition of two colors $A,B$ as follows. Start at color $A$. Move in the direction of the arrows by the number of steps needed to move from Red to color $B$. The color at which you arrive is the composition result.

For example, Yellow is two steps from Red, so composing Orange with Yellow gives Blue, which is two steps after Orange.

For two one-digit decimal numbers $x,y$, define their weird decimal XOR $x\diamond y$ as follows.

• The color of the result is the composition of the colors of $x$ and $y$.
• The state of the result is the bitwise XOR of the states of $x$ and $y$.

For example, $3$ is Orange with state $1$, while $6$ is Blue with state $0$. Composing Orange and Blue gives Purple, and $1\mathbin{\mathrm{XOR}}0=1$, so $3\diamond6=9$.

Extend the operation to nonnegative integers with multiple decimal digits. A missing higher digit is treated as $0$. The weird decimal XOR of two integers is obtained by independently applying the one-digit operation at every decimal position.

For example, the tens digit satisfies $3\diamond6=9$ and the ones digit satisfies $7\diamond8=5$, so $37\diamond68=95$.

When the operation is applied more than once, evaluate it from left to right. Thus,

You are given a sequence $A_1,A_2,\cdots,A_N$. Each query consists of two integers $L,R$. For each query, count the ordered pairs of integers $(l,r)$ satisfying both conditions below.

• $L\le l\le r\le R$.
• $A_l\diamond A_{l+1}\diamond\cdots\diamond A_r=0$.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ Q$ $A_1\ A_2\ \cdots\ A_N$ $L_1\ R_1$ $L_2\ R_2$ $\vdots$ $L_Q\ R_Q$

The $q$-th query asks about the interval $[L_q,R_q]$.

For each test case, for $q=1,2,\cdots,Q$ in order, print on its own line the number of ordered pairs $(l,r)$ satisfying the conditions of the $q$-th query.

Do not print an additional separator between test cases.

• $1 \le T \le 200\,000$.
• $1 \le N,Q \le 200\,000$.
• The sum of $N$ over all test cases does not exceed $200\,000$.
• The sum of $Q$ over all test cases does not exceed $200\,000$.
• $0 \le A_i \le 10^{18}$ ($1 \le i \le N$).
• $1 \le L_q \le R_q \le N$ ($1 \le q \le Q$).
• Every number in the input is an integer.