테트리스 생성

고전 테트리스는 떨어지는 테트로미노를 보드 위에 배치하는 게임이다. 테트로미노는 일곱 가지가 있고, 각각 모양이 닮은 글자 J, L, S, Z, I, O, T의 이름을 딴다.

원조 테트리스에서 플레이어는 테트로미노를 한 번에 하나씩 받았고, 각 테트로미노는 일곱 가지 중에서 독립적으로 균등하게 무작위로 선택되었다. 그래서 게임 중에 어떤 테트로미노 순서든 나타날 수 있었고, I 테트로미노가 연달아 여러 개 나오는 일도 있었다. 현대 테트리스는 테트로미노를 일곱 개씩 묶어 생성해서 이런 연속을 없앤다. 게임의 처음 일곱 테트로미노는 일곱 가지 테트로미노가 각각 하나씩, 무작위 순서로 나온다. 그다음 일곱 테트로미노도 일곱 가지가 각각 하나씩 무작위 순서로 나온다(처음 일곱 개의 순서와 같을 수도 있고 다를 수도 있다). 그다음 일곱 개도 마찬가지이고, 이후로도 계속 그렇다. 이 생성기에서도 같은 테트로미노가 연달아 두 번 나오는 것은 가능하지만(예를 들어 게임의 일곱 번째와 여덟 번째 테트로미노가 서로 같을 수 있다), 같은 종류가 연달아 세 번 나오는 것은 불가능하다.

테트로미노 순서가 주어질 때, 현대 테트리스 생성기가 게임의 어느 시점에서 그 순서를 만들 수 있는지 판정하라.

첫째 줄에 테스트 케이스의 수 $t$가 주어진다($1 \le t \le 10^5$).

다음 $t$개 줄에 각각 문자열 $s$가 하나씩 주어진다($1 \le |s| \le 1{,}000, s \in \{\texttt{J}, \texttt{L}, \texttt{S}, \texttt{Z}, \texttt{I}, \texttt{O}, \texttt{T}\}^\*$). 이 문자열은 테트로미노 순서를 나타내며, 각각이 하나의 테스트 케이스이다.

모든 테스트 케이스의 길이 합은 $10^5$를 넘지 않는다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 그 순서를 현대 테트리스 생성기가 만들 수 있으면 1, 그렇지 않으면 0이다.