E. Prefix Mahjong
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A positive integer multiset $$$s$$$ is a "Pong" if $$$s=\{x,x,x\}$$$ for some positive integer $$$x$$$.

A positive integer multiset $$$s$$$ is a "Chow" if $$$s=\{x,x+1,x+2\}$$$ for some positive integer $$$x$$$.

A positive integer multiset $$$s$$$ is an "Eyes" if $$$s=\{x,x\}$$$ for some positive integer $$$x$$$.

A positive integer sequence is a "Mahjong" if it can be divided into some (possibly zero) "Pong"s, some (possibly zero) "Chow"s, and exactly one "Eyes".

For example, sequence $$$s=\{1,1,4,5,1,4,4,3\}$$$ is a "Mahjong" because it can be divided into $$$\{1,1,1\}$$$, $$$\{4,5,3\}$$$, $$$\{4,4\}$$$.

For each prefix of a given positive integer sequence, determine if it is a "Mahjong".

Input

Each test contains multiple test cases. The first line contains a single interger $$$t$$$ ($$$1 \leq t \leq 10^5$$$), denoting the number of test cases.

For each test case, the only line contains an integer $$$n$$$ ($$$1\le n\le 10^5$$$) and the following $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1\le a_i\le 10^9$$$), denoting the length of the integer sequence and the elements of the positive integer sequence, respectively.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$10^5$$$.

Output

For each test case, print a string consisting of '0' and '1' in one line. The $$$i$$$-th character is '1' if the prefix of length $$$i$$$ is a "Mahjong"; otherwise it is '0'.

Examples
Input
4
8 1 1 4 5 1 4 4 3
14 1 1 3 5 4 2 5 5 4 6 6 2 2 4
17 3 5 3 2 2 3 3 1 4 3 1 3 3 5 2 4 4
8 2 4 11 11 14 8 6 3
Output
01000001
01001001000001
00000000001000001
00000000
Input
10
2 1 1
3 1 1 1
3 1 2 3
5 1 1 1 1 1
5 1 1 1 2 2
5 1 1 1 2 3
8 1 1 1 1 1 1 2 3
5 2 2 1 1 1
5 3 2 1 1 1
8 3 2 1 1 1 1 1 1
Output
01
010
000
01001
01001
01001
01001001
01001
00001
00001001