Description

比托蒂亚的国王 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 要求你编写一个程序，帮助将他的臣民的当前名字翻译成新名字。

如果你成功了，你可以作为奖励保留你现在的名字！

Input Format

第一行一个整数 $k$ 表示需要翻译的名字数量 ($1\leq k\leq20$)。

名字在接下来的行中给出，每行一个。

每个名字由不多于 $200000$ 个英文大写字母组成。

在 $30\%$ 的数据中，每个名字最多由 $20$ 个字母组成。

Output Format

你的程序应该向标准输出打印 $k$ 行。

每个连续的行应包含与输入中给出的名字对应的零和一的序列（中间没有空格）。

如果某些名字不存在合适的比特序列，则应为该名字打印 "XXX"（不带引号）。

3
ABIABUABIAB
BABBAB
BABURBAB

01001101001
010010
01000010

Hint

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