Periodicity

Byteasar, the king of Bitotia, has ordered a reform of his subjects' names. The names of Bitotians often contain repeating fragments. For example, the name Abiabuabiab contains two occurrences of the fragment abiab. Byteasar wants to replace each subject's name with a sequence of bits of the same length as the original name, and he would like the new name to reflect the repetitions of the original one.

For simplicity we treat upper-case and lower-case letters as identical. For a sequence $w = w_1 w_2 \dots w_k$ (of letters or bits), an integer $p$ with $1 \le p < k$ is called a period of $w$ if $w_i = w_{i+p}$ for every $i = 1, \dots, k - p$. Let $\mathrm{Per}(w)$ denote the set of all periods of $w$. For example, $\mathrm{Per}(\text{ABIABUABIAB}) = \{6, 9\}$, $\mathrm{Per}(01001010010) = \{5, 8, 10\}$, and $\mathrm{Per}(0000) = \{1, 2, 3\}$.

Byteasar decided that every name must be replaced by a sequence of bits that:

• has the same length as the original name,
• has exactly the same set of periods as the original name,
• is the lexicographically smallest bit sequence satisfying the two conditions above.

For example, ABIABUABIAB becomes 01001101001, BABBAB becomes 010010, and BABURBAB becomes 01000010.

Write a program that translates the subjects' current names into their new bit-sequence names.

The first line of standard input contains a single integer $k$, the number of names to translate ($1 \le k \le 20$). Each of the next $k$ lines contains one name. Every name consists of at least $1$ and at most $200\,000$ upper-case letters of the English alphabet.

In tests worth 30% of the points, every name has at most $20$ letters.

Print $k$ lines. The $i$-th line must contain the bit sequence (a string of 0s and 1s with no separators) corresponding to the $i$-th input name. If no suitable bit sequence exists for some name, print XXX (without the quotation marks) on that line instead.

A bit sequence $x_1 x_2 \dots x_k$ is lexicographically smaller than a bit sequence $y_1 y_2 \dots y_k$ if there is an index $i$ ($1 \le i \le k$) with $x_i < y_i$ and $x_j = y_j$ for all $j = 1, \dots, i - 1$.