A qubit is in one of the following four states.
There are three kinds of gates: H, X, and Z. They transform a qubit as follows.
H: swaps with , and swaps with .X: swaps with , and leaves and unchanged.A circuit contains gates in a line. For an interval , a qubit passes through gates in this order.
Count the intervals 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:
For each case, print the number of intervals satisfying the condition on one line.
Z: swaps with , and leaves and unchanged.Each case is given in the following format:
The -th character of denotes the -th gate.
HXZ