P3526 [POI 2011] OKR-Periodicity

比托蒂亚的国王 Byteasar 下令对他的臣民的名字进行改革。 比托蒂亚人的名字通常包含重复的短语，例如，名字 Abiabuabiab 包含两次出现的短语 abiab。Byteasar 打算将他的臣民的名字改为与原名长度相匹配的 01 串。 此外，他非常希望在新名字中反映原始的周期。 对于任何字符序列（字母或 01 串）$w = w_1w_2\cdots w_k$，我们说整数 $p\ (1\leq p < k)$ 是 $w$ 的周期，如果 $w_i = w_{i + p}$ 对于所有 $i = 1,\cdots,k - p$ 都成立。 我们用 $Per(w)$ 表示 $w$ 的所有周期的集合。 例如，$Per(\texttt{ABIABUABIAB})=\{6,9\},Per(\texttt{01001010010})=\{5,8,10\},Per(\texttt{0000})=\{1,2,3\}$。 Byteasar 决定将每个名字串 $S$ 改为一个 01 串 $T$，该串是满足 $|S|=|T|$ 且 $Per(S)=Per(T)$ 条件的字典序最小的 01 串。 例如，名字 `ABIABUABIAB` 应该改为 `01001101001`，`BABBAB` 改为 `010010`，`BABURBAB` 改为 `01000010`。 Byteasar 要求你编写一个程序，帮助将他的臣民的当前名字翻译成新名字。 如果你成功了，你可以作为奖励保留你现在的名字！

第一行一个整数 $k$ 表示需要翻译的名字数量 ($1\leq k\leq20$)。 名字在接下来的行中给出，每行一个。 每个名字由不多于 $200000$ 个英文大写字母组成。 在 $30\%$ 的数据中，每个名字最多由 $20$ 个字母组成。

你的程序应该向标准输出打印 $k$ 行。 每个连续的行应包含与输入中给出的名字对应的零和一的序列（中间没有空格）。 如果某些名字不存在合适的比特序列，则应为该名字打印 "XXX"（不带引号）。

对于 $100\%$ 的数据，$1\leq k\leq20$，单个名字长度不超过 $200000$。