在一场漫长的统计学讲座结束后，学生们正准备离开教室，突然下起了大雨。由于你没有带伞，你决定留在教室里，希望雨能快点停。几分钟后，教室里只剩下你一个人。你发现了一件有趣的事：黑板上写着 $N$ ($N$ 为奇数) 个不同的整数，它们排成一行。因为你感到非常无聊，你决定擦掉黑板上的这些数字，好让清洁工少做点工作。

粉笔和黑板。公有领域。

由于你刚刚在讲座中学习了中位数的概念，你发明了以下针对三个整数的“擦除操作”：擦掉三个数中的最大值和最小值，只留下这三个数的中位数。你决定重复以下过程：在黑板上选择三个连续的整数，并对它们执行擦除操作。执行此操作后，黑板上的整数个数会减少 2。最终，在重复该过程 $\frac{N-1}{2}$ 次后，黑板上将只剩下一个整数。突然，你产生了一个有趣的问题：哪些整数可能存留到最后？

输入格式

输入包含多个测试用例。输入的第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $N$ ($1 \le N \le 5000$，$N$ 为奇数)，表示黑板上初始的整数个数。第二行包含 $N$ 个不同的整数 $a_1, a_2, \dots, a_N$ ($1 \le a_i \le N$)，其中 $a_i$ ($1 \le i \le N$) 表示黑板上的第 $i$ 个整数。

保证所有测试用例的 $N$ 之和不超过 $10^4$。

输出格式

对于每个测试用例，输出一行，包含一个长度为 $N$ 的字符串。如果 $a_i$ ($1 \le i \le N$) 有可能成为最终剩下的唯一整数，则字符串的第 $i$ 个字符应为 '1'，否则应为 '0'。

样例

输入 1

2
5
3 1 2 5 4
3
2 3 1

输出 1

10001
100