Description

Byteasar, the king of Bitotia, has ordained a reform of his subjects' names. The names of Bitotians often contain repeating phrases, e.g., the name Abiabuabiab has two occurrences of the phrase abiab. Byteasar intends to change the names of his subjects to sequences of bits matching the lengths of their original names. Also, he would very much like to reflect the original repetitions in the new names.

In the following, for simplicity, we will identify the upper- and lower-case letters in the names. For any sequence of characters (letters or bits)W=W1W2...Wk we say that the integer P(1<=P<K) is a period of w if Wi=Wi+P for all i=1,...,k-p. We denote the set of all periods of w by Per(w). For example,Per(ABIABUABIAB={6,9}, Per(01001010010)={5,8,10}, andPer(0000)={1,2,3}.

Byteasar has decided that every name is to be changed to a sequence of bits that:

·        has length matching that of the original name,

·        has the same set of periods as the original name,

·        is the smallest (lexicographically¹) sequence of bits satisfying the previous conditions.

For example, the name ABIABUABIAB should be changed to 01001101001, BABBAB to 010010, and BABURBAB to 01000010.

Byteasar has asked you to write a program that would facilitate the translation of his subjects' current names into new ones. If you succeed, you may keep your current name as a reward!

给定一个字符串S，其长度为N，如果对于任意的i(1<=i<=n-t)有Si=Si+t(1<=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，表示这个数据里你要处理K个问题。 接下来K行，每行有一个仅包含大写字母并且长度不超过200000的字符串。 输出： 

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

Input

Output

Sample Input

Sample Output