这是本次比赛的最后一道题，所以 Rikka 不想在背景描述上浪费太多笔墨。让我们把问题描述得简单明了。

你有一个长度为 $n$ 的字符串 $s$，其中仅包含从 “a” 到 “l” 的小写英文字母（共有 12 种可能的字母）。你可以选择这 12 个字母的一个排列 $p_a, p_b, \dots, p_l$，然后构造字符串 $t = p_{s_1} p_{s_2} \dots p_{s_n}$。你的任务是对于每个 $i$（从 $1$ 到 $n$），判断在经过这样的修改后，第 $i$ 个后缀（即子串 $t[i, n]$）是否可能成为 $t$ 的所有后缀中字典序最大的一个。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。

每个测试用例占一行，包含一个字符串 $s$（$1 \le |s| \le 10^5$，字符串仅包含从 “a” 到 “l” 的小写英文字母）。

保证 $|s| > 10^3$ 的测试用例不超过 15 个。

输出格式

对于每个测试用例，输出一行长度为 $|s|$ 的二进制字符串。如果第 $i$ 个后缀能够成为字典序最大的后缀，则第 $i$ 位输出 “1”，否则输出 “0”。

样例

样例输入 1

3
abaab
abcdefghijkllkjihgfedcba
aabbcccbaabcca

样例输出 1

01100
111111111111011111111110
10101000100000