Problem E
Tetris Generation

The classic game Tetris involves arranging falling tetrominoes on a board. There are seven different tetrominoes, each named after a letter that resembles their shape: J, L, S, Z, I, O, and T.

In the original Tetris, the player would receive one tetromino at a time, and each tetromino would be chosen from among the seven possibilities independently and uniformly at random. This meant that any sequence of tetrominoes could appear in a game, such as numerous I tetrominoes in a row. Modern versions of Tetris remove these streaks by generating tetrominoes in groups of seven: The first seven tetrominoes in a game will be one of each of the seven different tetrominoes in a random order. The next seven tetrominoes will also be one of each of the seven different tetrominoes in a random order (possibly but not necessarily different from the ordering of the first seven). Same goes for the next seven, and so on and so forth. With this generator, it is still possible to get two of the same tetromino in a row (for example, the seventh and eighth tetrominoes in the game can be the same as each other), but it is not possible to get three of the same type in a row.

Given a sequence of tetrominoes, determine whether it is possible for a modern Tetris generator to produce that sequence at some point in a game.

Input

The first line of input contains an integer $t$ ($1 \le t \le 10^5$), which is the number of test cases.

Each of the next $t$ lines contains a single string $s$ ($1 \le |s| \le 1{,}000, s \in \{ \texttt{J}, \texttt{L}, \texttt{S}, \texttt{Z}, \texttt{I}, \texttt{O}, \texttt{T}\} ^*$). This string represents a sequence of tetrominoes, and is a single test case.

The sum of the lengths of all input test cases will not exceed $10^5$.

Output

For each test case, output a single line with a single integer, which is 1 if the sequence can be generated by a modern Tetris generator, and 0 otherwise.

2
JJTO
JJTT

1
0