#481 이상한 십진법 XOR

Statement

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

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

\text{빨강}\to\text{주황}\to\text{노랑}\to\text{파랑}\to\text{보라}\to\text{빨강}

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

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

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

예를 들어 $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은 앞에서부터 차례대로 계산한다. 즉,

a_1\diamond a_2\diamond\cdots\diamond a_k=(((a_1\diamond a_2)\diamond a_3)\diamond\cdots)\diamond a_k

로 정의한다.

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

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

$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	40	$0 \le A_i \le 9$ ( $1 \le i \le N$ ).
2	60	추가적인 제약이 없다.

입력

1
6
68 37 123 189 37 95
7
3
5
7
6
7

출력