The Qubit Returns

A qubit is in one of the following four states.

• $\lvert0\rangle$: the state $0$
• $\lvert1\rangle$: the state $1$
• $\lvert+\rangle$: a sum of $0$ and $1$
• $\lvert-\rangle$: a difference of $0$ and $1$

There are three kinds of gates: H, X, and Z. They transform a qubit as follows.

• H: swaps $\lvert0\rangle$ with $\lvert+\rangle$, and swaps $\lvert1\rangle$ with $\lvert-\rangle$.
• X: swaps $\lvert0\rangle$ with , and leaves and unchanged.

A circuit contains $N$ gates in a line. For an interval $[l,r]$, a qubit passes through gates $l,l+1,\cdots,r$ in this order.

Count the intervals $[l,r]$ for which each of the four states returns to its initial state after passing through the interval.

The input is given in the following format:

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

For each case, print the number of intervals satisfying the condition on one line.

• $1\leq T\leq10\,000$.
• $1\leq N\leq5\,000$.
• $S$ is a string of length consisting only of , , and .