이상한 십진법 XOR

예를 들어 빨강에서 노랑까지는 $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$.

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

$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]$에 대한 질문을 의미한다.

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