큐비트는 다음 네 상태 중 하나에 있다.
게이트는 H, X, Z의 세 종류이다. 각 게이트는 큐비트의 상태를 다음과 같이 바꾼다.
H: 과 을 서로 바꾸고, 과 을 서로 바꾼다.X: 과 을 서로 바꾸고, 과 은 바꾸지 않는다.개의 게이트가 일렬로 놓인 회로가 주어진다. 구간 을 고르면 큐비트는 번째 게이트부터 번째 게이트까지 차례로 통과한다.
네 상태가 각각 이 구간을 통과한 뒤 모두 처음 상태로 돌아오는 구간 의 개수를 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 케이스마다 조건을 만족하는 구간의 개수를 한 줄에 출력한다.
Z: 과 을 서로 바꾸고, 과 은 바꾸지 않는다.각 케이스는 다음과 같은 형식으로 주어진다.
의 번째 문자는 번째 게이트의 종류를 나타낸다.
HXZ