经典游戏俄罗斯方块（Tetris）涉及在棋盘上排列下落的四格骨牌（tetrominoes）。共有七种不同的四格骨牌，每种都以其形状所像的字母命名：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 \{J, L, S, Z, I, O, T\}^*$)。该字符串表示一个四格骨牌序列，为一个测试用例。

所有测试用例的长度之和不超过 $10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数，如果该序列可以由现代俄罗斯方块生成器产生，则输出 1，否则输出 0。

样例

样例输入 1

2
JJTO
JJTT

样例输出 1

1
0