Coco likes to stack chocolate ice cream to eat. A chocolate ice cream tower can be represented as a string consisting of uppercase English letters. For example, stacking Belgian, Mint, and Original flavors in order can be written as BMO.

Coco decided to define a "2-tier ice cream" as follows:

• Given an ice cream string $S$ of length $n$, consider the prefix $S'$ of $S$ with length $\left\lceil \frac{n}{2} \right\rceil$. $\left\lceil x \right\rceil$ is the smallest integer greater than or equal to $x$.
• $S$ is a 2-tier ice cream if it satisfies $S = S' + \operatorname{rev}(S')$ or $S = S' + \operatorname{tail}(\operatorname{rev}(S'))$. Here, $S_1+S_2$ denotes the concatenation of two strings, $\operatorname{rev}(S)$ denotes the string $S$ with its characters in reverse order, and $\operatorname{tail}(S)$ denotes the string $S$ with its first character removed.

However, disappointed that this definition is the same as the standard definition of a palindrome, Coco went a step further and defined a "3-tier ice cream":

• Given an ice cream string $S$ of length $n$, consider the prefix $S'$ of $S$ with length $\left\lceil \frac{n}{3} \right\rceil$.
• $S$ is a 3-tier ice cream if it satisfies at least one of the following:
  • $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')$

For example, DOTTODOT is a 3-tier ice cream because DOTTODOT = DOT + TOD + OT.

Determine whether each string is a 3-tier ice cream string.

Input

The first line contains the number of test cases $T$ ($1 \le T \le 1000$).

Each of the next $T$ lines contains a string consisting of uppercase English letters. The length of the string is between $6$ and $30$, inclusive.

Output

For each test case, output 1 if the given string is a 3-tier ice cream string, and 0 otherwise.

Examples

Input 1

8
XYYXXY
BANABAN
DOTTODOT
DADADADADA
RANDOM
HOTSHOT
CHOCOLATE
DADADADADADA

Output 1

1
1
1
1
0
0
0
0