题目描述

比特托尼亚国王巴泰萨尔颁布了一项改革臣民姓名的法令。比特托尼亚人的名字常包含重复短语，例如名字"$\text{Abiabuabiab}$"就包含两个重复的"$\text{abiab}$"短语。巴泰萨尔计划将臣民姓名改为比特序列，序列长度与原名相同，同时他非常希望在新名字中保留原有的重复特征。

下面，为了简单起见，我们将识别名称中的大写和小写字母。对于任何字符序列（字母或比特）$W=W_1,W_2,\ldots W_k$，如果对于所有$i=1,\ldots ,k-p$，$Wi=Wi+P$，则整数$P(1\le P<K)$是$W$的周期。我们用$Per(W)$表示$W$的所有周期的集合。例如：$Per(ABIABUABIAB=\{6,9\}, Per(01001010010)=\{5,8,10\},Per(0000)=\{1,2,3\}.$

$\text{Byteasar}$决定将每个名字都改为一系列比特：

• 长度与原始名称匹配；
• 具有与原始名称相同的时段集，
• 是满足前一个条件的最小（字典$^1$）比特序列

例如，应将名称$\text{ABIABUABIAB}$更改为$01001101001$，$\text{BABBAB}$更改为$010010$，$\text{BABUBAB}$更改为$010 00010$。

$\text{Byteasar}$要求你编写一个程序，将他的主题的当前名称翻译成新的名称。如果你成功了，你可以保留你现在的名字作为奖励！

题目解释

给定一个字符串$S$，其长度为$N$，如果对于任意的$i(1\le i\le n-t)$有$S_i=S_i+t(1\le t<n-1)$，那么称其满足性质$g(T)$。定义$Per(S)$为所有使得$S$满足性质$g(T)$的整数$T$的集合。

例如：$Per(ABIABUABIAB)=\{6,9\}, Per(01001010010)=\{5,8,10\}, Per(0000)=\{1,2,3\}$. 你的任务是构造一个长度恰好为$N$的$01$串，使得： 第一，该串的$Per$集合和$S$相等。 第二，在所有满足条件$1$的$01$串中，该串的字典序最小。

输入格式

在标准输入的第一行中，有一个整数$k$——要翻译的名称数量。名称在以下行中给出，每行一个。每个名字由不少于且不超过$2\times 10^5$ 大写字母（英语字母）组成。

输出格式

您的程序应该将行打印到标准输出。每一行应包含与输入上给出的名称对应的$0$和$1$序列（中间没有空格）。如果某些名称不存在适当的位序列，则应为该名称打印"XXX"（不带引号）。

样例

3
ABIABUABIAB
BABBAB
BABURBAB

01001101001
010010
01000010

数据规模与约定

$1$比特序列$I_1,I_2,…,I_k$在字典上小于比特序列$Y_1,Y_2,…Y_k$，如果对于某些$i(1\le i\le k)$，我们有$Li$;

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

对于$100\%$的数据：$1\le k\le 20$。