题目描述

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

例如：$\operatorname{Per}(\texttt{ABIABUABIAB})=\{6,\ 9\}$，$\operatorname{Per}(\texttt{01001010010})=\{5,\ 8,\ 10\}$，$\operatorname{Per}(\texttt{0000})=\{1,\ 2,\ 3\}$。你的任务是构造一个长度恰好为 $N$ 的 01 串，使得

• 该串的 $\operatorname{Per}$ 集合和 $S$ 相等。
• 在所有满足条件 1 的 01 串中，该串的字典序最小。

输入格式

第一行是一个整数 $K$，表示这个数据里你要处理 $K$ 个问题。

接下来 $K$ 行，每行有一个仅包含大写字母并且长度不超过 $200000$ 的字符串。

输出格式

$K$ 行，第 $I$ 行对应输入的第 $i$ 个字符串的答案。如果不存在这样的 01 串，输出 XXX。

3
ABIABUABIAB
BABBAB
BABURBAB

01001101001
010010
01000010

来源

鸣谢 Object022。