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.List;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
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;
        FastScanner in = new FastScanner(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, FastScanner in, PrintWriter out) {
            int numTests = in.nextInt();
            for (int test = 0; test < numTests; test++) {
                int n = in.nextInt();
                int[] a = new int[n];
                int[] am = new int[n];
                for (int i = 0; i < n; i++) {
                    a[i] = in.nextInt() - 1;
                    ++am[a[i]];
                }
                boolean perm = true;
                for (int i = 0; i < n; i++) {
                    if (am[i] != 1) {
                        perm = false;
                    }
                }
                int[] prev = new int[n];
                int[] stack = new int[n];
                int sp = 0;
                for (int i = 0; i < n; i++) {
                    while (sp > 0 && a[stack[sp - 1]] >= a[i]) {
                        --sp;
                    }
                    if (sp > 0) {
                        prev[i] = stack[sp - 1];
                    } else {
                        prev[i] = -1;
                    }
                    stack[sp++] = i;
                }
                int[] next = new int[n];
                sp = 0;
                for (int i = n - 1; i >= 0; i--) {
                    while (sp > 0 && a[stack[sp - 1]] > a[i]) {
                        --sp;
                    }
                    if (sp > 0) {
                        next[i] = stack[sp - 1];
                    } else {
                        next[i] = n;
                    }
                    stack[sp++] = i;
                }

                List<Integer>[] events = new List[n + 3];
                for (int i = 0; i < events.length; i++) {
                    events[i] = new ArrayList<>();
                }
                for (int i = 0; i < n; i++) {
                    int id = a[i] + 1;
                    if (prev[i] + 1 == i) {
                        // add to segment [1, next[i] - i]
                        events[1].add(id);
                        events[next[i] - i + 1].add(-id);
                    } else if (i + 1 == next[i]) {
                        // add to segment [1, i - prev[i]]
                        events[1].add(id);
                        events[i - prev[i] + 1].add(-id);
                    } else {
                        // add to point (next[i] - prev[i] - 1)
                        int x = next[i] - prev[i] - 1;
                        events[x].add(id);
                        events[x + 1].add(-id);
                    }
                }

                FenwickTree tree = new FenwickTree(n);
                int[] cur = new int[n];
                char[] ans = new char[n];
                for (int k = 1; k <= n; k++) {
                    for (int id : events[k]) {
                        int i = Math.abs(id) - 1;
                        boolean wasOn = cur[i] == 1;
                        if (id > 0) {
                            ++cur[i];
                        } else {
                            --cur[i];
                        }
                        boolean nowOn = cur[i] == 1;
                        if (wasOn != nowOn) {
                            if (wasOn) {
                                tree.add(i, -1);
                            } else {
                                tree.add(i, 1);
                            }
                        }
                    }
                    int l = 0;
                    int r = n;
                    while (r - l > 1) {
                        int m = (l + r) / 2;
                        if (tree.sum(m - 1) == m) {
                            l = m;
                        } else {
                            r = m;
                        }
                    }
                    ans[k - 1] = (l >= n - k + 1) ? '1' : '0';
                }
                ans[0] = perm ? '1' : '0';
                out.println(new String(ans));
            }
        }

        class FenwickTree {
            int[] a;

            FenwickTree(int n) {
                a = new int[n];
            }

            public void add(int pos, int val) {
                while (pos < a.length) {
                    a[pos] += val;
                    pos |= pos + 1;
                }
            }

            public int sum(int r) {
                int res = 0;
                while (r >= 0) {
                    res += a[r];
                    r = (r & (r + 1)) - 1;
                }
                return res;
            }

        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

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

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

    }
}

