이상한 십진법 XOR

십진 숫자 $0,1,\cdots,9$를 다음과 같이 다섯 가지 색과 두 가지 상태로 나눈다.

다섯 색은 다음 순서로 원형으로 배치되어 있다.

두 색 $A,B$의 합성을 다음과 같이 정의한다. 색 $A$에서 시작하여, 빨강에서 색 $B$까지 위 화살표를 따라 이동하는 데 필요한 칸 수만큼 같은 방향으로 이동한다. 도착한 색이 합성 결과이다.

예를 들어 빨강에서 노랑까지는 $2$칸이므로, 주황과 노랑을 합성하면 주황에서 $2$칸 이동한 파랑이 된다.

두 한 자리 십진 숫자 $x,y$의 이상한 십진법 XOR $x\diamond y$를 다음과 같이 정의한다.

• 결과의 색은 $x$의 색과 $y$의 색을 합성한 색이다.
• 결과의 상태는 $x$의 상태와 $y$의 상태를 비트 XOR한 값이다.

예를 들어 $3$은 주황, 상태 $1$이고 $6$은 파랑, 상태 $0$이다. 주황과 파랑을 합성하면 보라이고 $1\mathbin{\mathrm{XOR}}0=1$이므로 $3\diamond6=9$이다.

이 연산을 여러 자리의 음이 아닌 정수에도 확장한다. 존재하지 않는 높은 자리의 숫자는 $0$으로 생각한다. 두 수의 각 십진 자리에서 독립적으로 이상한 십진법 XOR을 수행한 결과를 두 수의 이상한 십진법 XOR로 정의한다.

예를 들어 십의 자리에서 $3\diamond6=9$이고, 일의 자리에서 $7\diamond8=5$이므로 $37\diamond68=95$이다.

여러 번의 이상한 십진법 XOR은 앞에서부터 차례대로 계산한다. 즉,

로 정의한다.

길이가 $N$인 수열 $A_1,A_2,\cdots,A_N$이 주어진다. 각 쿼리는 두 정수 $L,R$로 이루어진다. 각 쿼리마다 다음 조건을 모두 만족하는 정수 순서쌍 $(l,r)$의 개수를 구하여라.

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

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

$q$번 쿼리는 구간 $[L_q,R_q]$에 대한 질문을 의미한다.

각 테스트 케이스에서 $q=1,2,\cdots,Q$의 순서대로, $q$번 쿼리의 조건을 만족하는 순서쌍 $(l,r)$의 개수를 한 줄에 하나씩 출력한다.

서로 다른 테스트 케이스의 출력 사이에 별도의 구분자는 출력하지 않는다.

• $1 \le T \le 200\,000$.
• $1 \le N,Q \le 200\,000$.
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.
• 모든 테스트 케이스에 대한 $Q$의 합은 $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$).
• 입력으로 주어지는 모든 수는 정수이다.