Three-Tier Chocolate Ice Cream

Coco likes to stack chocolate ice cream scoops and eat them. A stack of chocolate ice cream can be written as a string of uppercase English letters. For example, a stack of Belgian, mint, and original flavors, from bottom to top, can be written as BMO.

Coco defined a "two-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 two-tier ice cream if $S=S'+\operatorname{rev}(S')$ or $S=S'+\operatorname{tail}(\operatorname{rev}(S'))$. Here $S\_1+S\_2$ is the concatenation of $S\_1$ and $S\_2$ in that order, $\operatorname{rev}(S)$ is $S$ with its characters in reverse order, and $\operatorname{tail}(S)$ is $S$ with its first character removed.

Disappointed that this definition is the same as the ordinary definition of a palindrome, Coco defined a further step, the "three-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 three-tier ice cream if at least one of the following holds.
  • $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 = DOT + TOD + OT, so it is a three-tier ice cream.

Determine whether each given string is a three-tier ice cream string.

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

Each of the next $T$ lines contains a string of uppercase English letters. The length of each string is at least $6$ and at most $30$.

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