양자는 다시 제자리로

큐비트는 다음 네 상태 중 하나에 있다.

• $\lvert0\rangle$: $0$인 상태
• $\lvert1\rangle$: $1$인 상태
• $\lvert+\rangle$: $0$과 $1$이 더하기로 섞인 상태
• $\lvert-\rangle$: $0$과 $1$이 빼기로 섞인 상태

게이트는 H, X, Z의 세 종류이다. 각 게이트는 큐비트의 상태를 다음과 같이 바꾼다.

• H: $\lvert0\rangle$과 $\lvert+\rangle$을 서로 바꾸고, $\lvert1\rangle$과 $\lvert-\rangle$을 서로 바꾼다.
• X: $\lvert0\rangle$과 을 서로 바꾸고, 과 은 바꾸지 않는다.

$N$개의 게이트가 일렬로 놓인 회로가 주어진다. 구간 $[l,r]$을 고르면 큐비트는 $l$번째 게이트부터 $r$번째 게이트까지 차례로 통과한다.

네 상태가 각각 이 구간을 통과한 뒤 모두 처음 상태로 돌아오는 구간 $[l,r]$의 개수를 구하여라.

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

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

각 케이스마다 조건을 만족하는 구간의 개수를 한 줄에 출력한다.

• $1\leq T\leq10\,000$.
• $1\leq N\leq5\,000$.
• $S$는 , , 로만 이루어진 길이 의 문자열이다.