该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

保护伞公司的董事会会议室内有一个圆桌，\(n\)个董事坐成一个圆圈，每个董事属于一个阵营。
对于每个\(k(0<=k<n)\)，问能否去掉连续的\(k\)个人，使得余下的人中，任意两个相邻的人属于不同阵营。
请注意，余下的人仍形成一个环，每个人都有两个相邻的人。

Format

Input

每个测试点包含多组输入数据。
第一行一个整数\(T\)，表示数据组数。
每组数据第一行一个整数\(n(1<=n<=10^6)\)。
接下来一行\(n\)个整数，第\(i\)个整数\(c_i(1<=c_i<=10^6)\)表示第\(i\)个人所属的阵营。
所有数据中\(n\)的总和不超过\(10^6\)。

Output

按照输入顺序，对于每组数据输出一行一个字符串表示答案。
字符串的第\(i(0<=i<n)\)位为\(1\)当且仅当能去掉连续的\(i\)个人。

Sample 1

Input

4
3
1 1 2
5
1 1 1 1 1
4
1 2 1 3
4
1 2 1 2

Output

011
00001
1111
1011

Limitation

1s, 512MB for each test case.

Source

Vijos Original