题目描述

规则是这样的:每次生牛哥可以选择一个字符串，然后生牛哥选择一个正整数 $\red{t，}$系统会给生牛哥一个长度为$\red{t}$的圆环。然后生牛哥在圆环上选择一个起点，从字 符串第一个字母开始将这个字符串按顺时针在圆环上放置字母。一旦碰到下一个要放的位置已经有字母且要放进去的字母和原来已有的字母不同那么生牛哥就不能接着放了。

例如串为$\red{"①②③①②①②③"}$只能放进前五个，第六个$\red①$和已经存在的$\red③$不同所以不能再放。

假如生牛哥成功地把整个串都放进去了的话那么他就可以消除这个串并获得分数。我们称满足这个条件的$\red{t}$为"可行 $\red{t}$"。

但是这次$\red{t}$并不是越大越好了，而是对于不同的可行的$\red{t}$集合得分都不同。

生牛哥已经找到了这样一个串，它的可行$\red{t}$集合所得到的分数是最优的。但是选择字串的代价是和这个数的字典序有关系的。

所以生牛哥找到了你。

你需要最小化一个$\red{01}$串的字典序使得它满足以下两个条件:

$\red{1.}$该 $\red{01 }$串和生生哥给出的字串长度相等。

$\red{2.}$该 $\red{01 }$串和生牛哥给出的字串拥有同样的可行的$\red{t}$集合。

输入格式

第一行$\red{n}$表示数据组数。

接下来每行一个字符串。(只包含大写字母)

输出格式

每组数据输出一个 $\red{01}$串。

样例

输入样例

3

YDYYDY

JRYJREJRYJR

YDYAKYDY

输出样例

010010

01001101001

01000010

提示