19008번 - Rikka with String 다국어

문제

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_{\texttt{a}}, p_{\texttt{b}}, \ldots, p_{\texttt{l}},ドル and then consider the string $t = p_{s_1} p_{s_2} \ldots p_{s_n}$. Your task is to check for each $i$ from 1ドル$ to $n$ whether the $i$-th suffix (the substring $t[i, n]$) can become the largest suffix of $t$ in lexicographical order after such modification.

입력

The first line contains a single integer $t$ (1ドル \leq t \leq 10^3$), the number of test cases.

Each test case is given on a separate line containing a string $s$ (1ドル \leq |s| \leq 10^5,ドル the string contains only lowercase English letters from "a" to "l").

It is guaranteed that there are at most 15ドル$ test cases with $|s| > 10^3$.

출력

For each test case, output a single line with a binary string of length $|s|$. If the $i$-th suffix can become the largest one, the $i$-th position must contain "1". Otherwise, it must contain "0".

제한

힌트