Coco 喜欢叠着吃巧克力冰淇淋。巧克力冰淇淋塔可以用一个由大写英文字母组成的字符串来表示。例如，按顺序叠放比利时（Belgium）、薄荷（Mint）、原味（Original）口味的冰淇淋可以写成 BMO。

Coco 决定将“2段冰淇淋”定义如下：

• 给定一个长度为 $n$ 的冰淇淋字符串 $S$，考虑 $S$ 的长度为 $\left\lceil \frac{n}{2} \right\rceil$ 的前缀 $S'$。其中 $\left\lceil x \right\rceil$ 表示大于或等于 $x$ 的最小整数。
• 如果满足 $S = S' + \operatorname{rev}(S')$ 或 $S = S' + \operatorname{tail}(\operatorname{rev}(S'))$，则 $S$ 是一个 2段冰淇淋。这里 $S_1+S_2$ 表示将两个字符串按顺序拼接，$\operatorname{rev}(S)$ 表示将 $S$ 的字符顺序反转，$\operatorname{tail}(S)$ 表示移除 $S$ 的第一个字符。

然而，Coco 对这个定义与普通的回文（palindrome）定义相同感到失望，于是更进一步定义了“3段冰淇淋”。

• 给定一个长度为 $n$ 的冰淇淋字符串 $S$，考虑 $S$ 的长度为 $\left\lceil \frac{n}{3} \right\rceil$ 的前缀 $S'$。

• 如果满足以下条件中的至少一个，则 $S$ 是一个 3段冰淇淋：

  • $S = S' + \operatorname{rev}(S') + S'$
  • $S = S' + \operatorname{tail}(\operatorname{rev}(S')) + S'$
  • $S = S' + \operatorname{rev}(S') + \operatorname{tail}(S')$
  • $S = S' + \operatorname{tail}(\operatorname{rev}(S')) + \operatorname{tail}(S')$

例如，DOTTODOT 是一个 3段冰淇淋，因为 DOTTODOT = DOT + TOD + OT。

请判断给定的每个字符串是否为 3段冰淇淋字符串。

输入格式

第一行包含测试数据组数 $T$（$1 \le T \le 1000$）。

接下来的 $T$ 行，每行包含一个由大写英文字母组成的字符串。字符串的长度在 $6$ 以上 $30$ 以下。

输出格式

对于每组测试数据，如果给定的字符串是 3段冰淇淋字符串，则输出 1，否则输出 0。

样例

输入样例 1

8
XYYXXY
BANABAN
DOTTODOT
DADADADADA
RANDOM
HOTSHOT
CHOCOLATE
DADADADADADA

输出样例 1

1
1
1
1
0
0
0
0