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.BufferedInputStream;
import java.util.*;

/**
 * @Author hello_kiss
 * @Date 2020/12/7 0:06
 */
public class D {
    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        int t=scan.nextInt();
        while(t-->0){
            int n=scan.nextInt();
            int []a=new int[n];
            for(int i=0;i<n;i++)a[i]=scan.nextInt();
            Stack<Integer>stack=new Stack<>();
            int []l=new int[n];
            int []r=new int[n];
            for(int i=0;i<n;i++){
                while(!stack.isEmpty()&&a[stack.peek()]>=a[i])stack.pop();
                if(stack.isEmpty())l[i]=0;
                else l[i]=stack.peek()+1;
                stack.push(i);
            }
            stack.clear();
            for(int i=n-1;i>=0;i--){
                while(!stack.isEmpty()&&a[stack.peek()]>=a[i])stack.pop();
                if(stack.isEmpty())r[i]=n-1;
                else r[i]=stack.peek()-1;
                stack.push(i);
            }
            int []flag=new int[n+1];
            for(int i=0;i<n;i++){
                flag[a[i]]=Math.max(flag[a[i]],r[i]-l[i]+1);
            }
            List<Node> list=new ArrayList<>();
            for(int i=1;i<=n;i++){
                if(flag[i]>0){
                    Node node=new Node(i,flag[i]);
                    list.add(node);
                }
            }
            Collections.sort(list,(x,y)->{
                if(x.gs==y.gs)return x.val-y.val;
                return y.gs-x.gs;
            });
            int ma[]=new int[n];
            for(int i=0;i<list.size();i++){
                ma[i]=list.get(i).val;
                if(i>0)
                ma[i]=Math.max(ma[i-1],list.get(i).val);
            }
            int sub=0;
            int ans[]=new int[n+1];
            int index=list.size()-1;
//            for(int i=0;i<=index;i++){
//                System.out.printf("%d %d\n",list.get(i).val,list.get(i).gs);
//            }
            for(int i=1;i<=n;i++){
                if(list.size()<n-i+1){
                    ans[i]=0;
                }
                else{
                    while(index>=0&&list.get(index).gs<=sub)index--;
                    if(index<0)ans[i]=0;
                    else{
                        if(index+1==n-i+1&&ma[index]==n-i+1){
                            ans[i]=1;
                        }
                        else ans[i]=0;
                    }
                }
                sub++;
            }
            for(int i=1;i<=n;i++) System.out.printf("%d",ans[i]);
            System.out.println();

        }
    }
    private static class Node{
        public int val,gs;
        public Node(int val,int gs){
            this.val=val;
            this.gs=gs;
        }
    }
}
