Bitotia 的国王 Byteasar 下令改革他臣民的名字。Bitotians 的名字中经常包含重复的短语，例如名字 Abiabuabiab 中出现了两次 abiab。Byteasar 打算将他臣民的名字改为与原名长度相同的比特序列。此外，他非常希望在新的名字中反映出原有的重复规律。

为简单起见，我们将名字中的大小写字母视为相同。对于任何字符（字母或比特）序列 $w=w_{1}w_{2}\dots w_{k}$，如果对于所有 $i=1,\dots,k-p$ 都有 $w_{i}=w_{i+p}$，则称整数 $p$ ($1 \le p < k$) 为 $w$ 的一个周期。我们将 $w$ 的所有周期集合记为 $\text{Per}(w)$。例如，$\text{Per}(\texttt{ABIABUABIAB})=\{6,9\}$，$\text{Per}(\texttt{01001010010})=\{5,8,10\}$，以及 $\text{Per}(\texttt{0000})=\{1,2,3\}$。

Byteasar 决定将每个名字改为一个比特序列，该序列需满足：

• 长度与原名相同，
• 具有与原名相同的周期集合，
• 是满足上述条件的所有比特序列中字典序最小的$^{1}$。

例如，名字 ABIABUABIAB 应改为 01001101001，BABBAB 改为 010010，BABURBAB 改为 01000010。

Byteasar 请你编写一个程序，帮助将他臣民当前的名字转换为新的名字。如果你成功了，作为奖励，你可以保留你现在的名字！

$^{1}$：如果对于某个 $i$ ($1 \le i \le k$)，有 $x_{i} < y_{i}$ 且对于所有 $j=1,\dots,i-1$ 都有 $x_{j}=y_{j}$，则称比特序列 $x_{1}x_{2}\dots x_{k}$ 在字典序上小于比特序列 $y_{1}y_{2}\dots y_{k}$。

输入格式

标准输入的第一行包含一个整数 $k$，表示需要转换的名字数量 ($1 \le k \le 20$)。接下来的每一行包含一个名字。每个名字由 $1$ 到 $200\,000$ 个大写英文字母组成。

在占总分 $30\%$ 的测试数据中，每个名字的长度不超过 $20$ 个字母。

输出格式

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

样例

样例输入 1

3
ABIABUABIAB
BABBAB
BABURBAB

样例输出 1

01001101001
010010
01000010