On the competitive programming platform CodeCook, every person has a rating graph described by an array of integers a of length n. You are now updating the infrastructure, so you've created a program to compress these graphs.

The program works as follows. Given an integer parameter k, the program takes the minimum of each contiguous subarray of length k in a.

More formally, for an array a of length n and an integer k, define the k-compression array of a as an array b of length n-k+1, such that $$$b_j =min_{j≤ i≤ j+k-1}a_i$$$

For example, the 3-compression array of [1, 3, 4, 5, 2] is [min\{1, 3, 4\}, min\{3, 4, 5\}, min\{4, 5, 2\}]=[1, 3, 2].

A permutation of length m is an array consisting of m distinct integers from 1 to m in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (m=3 but there is 4 in the array).

A k-compression array will make CodeCook users happy if it will be a permutation. Given an array a, determine for all 1≤ k≤ n if CodeCook users will be happy after a k-compression of this array or not.

Input

The first line contains a single integer t (1≤ t≤ 10^4) — the number of test cases.

The first line of the description of each test case contains a single integer n (1≤ n≤ 3⋅ 10^5) — the length of the array.

The second line of the description of each test case contains n integers a_1,…,a_n (1≤ a_i≤ n) — the elements of the array.

It is guaranteed, that the sum of n for all test cases does not exceed 3⋅ 10^5.

Output

For each test case, print a binary string of length n. 

The k-th character of the string should be 1 if CodeCook users will be happy after a k-compression of the array a, and 0 otherwise. 

Example

Input


5
5
1 5 3 4 2
4
1 3 2 1
5
1 3 3 3 2
10
1 2 3 4 5 6 7 8 9 10
3
3 3 2


Output


10111
0001
00111
1111111111
000

Note

In the first test case, a=[1, 5, 3, 4, 2].

  * The 1-compression of a is [1, 5, 3, 4, 2] and it is a permutation. 
  * The 2-compression of a is [1, 3, 3, 2] and it is not a permutation, since 3 appears twice. 
  * The 3-compression of a is [1, 3, 2] and it is a permutation. 
  * The 4-compression of a is [1, 2] and it is a permutation. 
  * The 5-compression of a is [1] and it is a permutation. 
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Comparator;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int T = in.nextInt();
            while (T-- > 0) {
                int N = in.nextInt();
                int[] arr = new int[N];
                ArrayList<Integer> perm = new ArrayList<>();
                for (int i = 0; i < N; i++) {
                    arr[i] = in.nextInt() - 1;
                    perm.add(i);
                }
                Collections.sort(perm, new Comparator<Integer>() {

                    public int compare(Integer integer, Integer t1) {
                        return Integer.compare(arr[integer], arr[t1]);
                    }
                });


                TreeSet<Integer> set = new TreeSet<Integer>();
                set.add(-1);
                set.add(N);
                ArrayList<Integer>[] solo = new ArrayList[N];
                int[][] h = new int[N][2];
                for (int i = 0; i < N; i++) {
                    Arrays.fill(h[i], -1);
                    solo[i] = new ArrayList<>();
                }

                for (int i : perm) {
                    int low = set.lower(i);
                    int high = set.higher(i);
                    if (i == low + 1 || i == high - 1) {
                        if ((high - 1) - (low + 1) + 1 > h[arr[i]][0]) {
                            h[arr[i]][1] = h[arr[i]][0];
                            h[arr[i]][0] = (high - 1) - (low + 1) + 1;
                        }
                    } else {
                        solo[arr[i]].add((high - 1) - (low + 1) + 1);
                    }
                    set.add(i);
                }
                for (int i = 0; i < N; i++) {
                    int max = -1;
                    for (int e : solo[i]) {
                        max = Math.max(max, e);
                    }
                    int e = max;
                    if (h[i][1] <= e && e <= h[i][0]) {
                        h[i][1] = e;
                    } else if (e == h[i][1] - 1) {
                        h[i][1]--;
                    } else if (e > h[i][0]) {
                        h[i][0] = e;
                        h[i][1] = e;
                    }
                }
                int lb = -1;
                int hb = N;
                char[] ans = new char[N];
                boolean[] bad = new boolean[N + 1];
                Arrays.fill(ans, '0');
                ans[0] = '1';
                for (int i = 0; i < N; i++) {
                    if (i != arr[perm.get(i)]) {
                        ans[0] = '0';
                    }
                    int K = (N - i);
                    lb = Math.max(h[i][1], lb);
                    hb = Math.min(h[i][0], hb);
                    if (lb <= K && K <= hb) {
                        if (!bad[K]) {
                            ans[K - 1] = '1';
                        }
                    }
                }
                out.println(new String(ans));
            }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

