L. [POI2011] Periodicity

Bitotia 国王 Byteasar 宣布了要对他臣民的名字进行改革。Bitotia 人的名字经常包含重复的短语，例如名字「Abiabuabiab」中短语「abiab」出现了两次。Byteasar 试图将他的臣民的名字改成和他们之前名字一样长的 串。并且他十分希望新名字也能反映之前名字的重复规律。

接下来，为了简化说明，我们将区分字母的大小写。对于任意字符（字母或 ）序列 ，如果存在一个整数 ，对于所有 都有 ，则整数 是 的一个周期。我们记 的所有周期的集合为 。比如，。

Byteasar 决定了每个名字都要变成一个满足以下条件的 串：

= 长度和原来的名字相同；

• 和之前名字有相同的周期集合；

• 在满足前两个条件的情况下字典序最小。

比如，ABIABUABIAB 这个名字应变为 01001101001，BABBAB 变为 010010，BABURBAB 变为 01000010。

Byteasar 要求你写一个程序，以帮助他将其臣民的名字转换为新名字。如果你成功了，作为奖赏你可以保留你目前的名字！

第一行包含一个整数 ，表示要转换的名字个数；

接下来 行，每行一个要转换的名字。每个名字长度都在 到 之间，并且只包含英文大写字母。

输出 行，每行包含一个 串，如果存在一个合法的转换方案，则输出字典序最小的一个，否则输出 XXX。

输入样例

3
ABIABUABIAB
BABBAB
BABURBAB

输出样例

01001101001
010010
01000010

对于全部数据，。