Problem Description

This is the last problem of this contest, so Rikka doesn't want to add a lengthy background to it. Let us make all the things simple and clear.

You have a string $s$ of length $n$ which only contains lowercase English letters from a to l (There are $12$ possible letters). You can choose a permutation of these $12$ letters $p_a,p_b,...,p_l$ and then you can get a string $t = p_{s_1}p_{s_2}...p_{s_n}$. Your task is to check whether the $i$th suffix (the substring $s[i,n]$) can become the largest suffix in lexicographic order after this modification.

Input

The first line contains a single number $t(1 \leq t \leq 10^3)$, the number of testcases.

For each testcase, the first line contains a string $s(1 \leq |s| \leq 10^5)$.

The input guarantees that there are at most $15$ testcases with $|s| > 10^3$.

Output

For each testcase, output a single line with a $01$ string of length $|s|$. If the $i$th suffix can become the largest one, the $i$th position should be $1$. Otherwise, it should be $0$.

3
abaab
abcdefghijkllkjihgfedcba
aabbcccbaabcca

01100
111111111111011111111110
10101000100000