The sequence of m integers is called the permutation if it contains all integers from 1 to m exactly once. The number m is called the length of the permutation.

Dreamoon has two permutations p_1 and p_2 of non-zero lengths l_1 and l_2.

Now Dreamoon concatenates these two permutations into another sequence a of length l_1 + l_2. First l_1 elements of a is the permutation p_1 and next l_2 elements of a is the permutation p_2. 

You are given the sequence a, and you need to find two permutations p_1 and p_2. If there are several possible ways to restore them, you should find all of them. (Note that it is also possible that there will be no ways.)

Input

The first line contains an integer t (1 ≤ t ≤ 10 000) denoting the number of test cases in the input.

Each test case contains two lines. The first line contains one integer n (2 ≤ n ≤ 200 000): the length of a. The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n-1).

The total sum of n is less than 200 000.

Output

For each test case, the first line of output should contain one integer k: the number of ways to divide a into permutations p_1 and p_2.

Each of the next k lines should contain two integers l_1 and l_2 (1 ≤ l_1, l_2 ≤ n, l_1 + l_2 = n), denoting, that it is possible to divide a into two permutations of length l_1 and l_2 (p_1 is the first l_1 elements of a, and p_2 is the last l_2 elements of a). You can print solutions in any order.

Example

Input


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


Output


2
1 4
4 1
1
4 2
0
0
1
2 10
0

Note

In the first example, two possible ways to divide a into permutations are \{1\} + \{4, 3, 2, 1\} and \{1,4,3,2\} + \{1\}.

In the second example, the only way to divide a into permutations is \{2,4,1,3\} + \{2,1\}.

In the third example, there are no possible ways.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.InputMismatchException;
import java.util.*;
import java.io.*;
import java.lang.*;
public class Main{
    public static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
     
        public int read() {
            if (numChars==-1)
                throw new InputMismatchException();
     
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                }
                catch (IOException e) {
                    throw new InputMismatchException();
                }
     
                if(numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
     
        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() {
            int c = read();
     
            while(isSpaceChar(c))
                c = read();
     
            int sgn = 1;
     
            if (c == '-') {
                sgn = -1;
                c = read();
            }
     
            int res = 0;
            do {
                if(c<'0'||c>'9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
     
            return res * sgn;
        }
     
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
     
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }
     
        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
     
        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));
     
            return res.toString();
        }
     
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
     
        public String next() {
            return readString();
        }
     
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
 
    static long gcd(long a, long b){
        if (a == 0)
            return b;  
        return gcd(b % a, a);  
    }
    static long lcm(long a, long b)  {
        return (a*b)/gcd(a, b);  
    }
    public static void sortbyColumn(int arr[][], int col) 
    { 
        
        Arrays.sort(arr, new Comparator<int[]>() { 
            
          @Override              
          
          public int compare(final int[] entry1,  
                             final int[] entry2) { 
  
            
            if (entry1[col] > entry2[col]) 
                return 1; 
            else
                return -1; 
          } 
        });  
    } 
    static long func(long a[],long size,int s){
        long max1=a[s];
        long maxc=a[s];
        for(int i=s+1;i<size;i++){
            maxc=Math.max(a[i],maxc+a[i]);
            max1=Math.max(maxc,max1);
        }
        return max1;
    }
    public static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
        public U first;
        public V second;
    
        public Pair(U first, V second) {
            this.first = first;
            this.second = second;
        }
    
        public int hashCode() {
            return (first == null ? 0 : first.hashCode() * 31) + (second == null ? 0 : second.hashCode());
        }
    
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pair<U, V> p = (Pair<U, V>) o;
            return (first == null ? p.first == null : first.equals(p.first)) && (second == null ? p.second == null : second.equals(p.second));
        }
    
        public int compareTo(Pair<U, V> b) {
            int cmpU = first.compareTo(b.first);
            return cmpU != 0 ? cmpU : second.compareTo(b.second);
        }
    
        public String toString() {
            return String.format("(%s, %s)", first.toString(), second.toString());
        }
    
    }
    static LinkedList<Integer> li[]=new LinkedList[100001];
    static int ans1=0,ans2=0,max1=-1;
    static int dist[]=new int[100001];
    static int visited[]=new int[100001];
    //static int arr[];
    static ArrayList<Integer> adj[]=new ArrayList[100001];
    static void bfs(int n,int m){
        //visited[x]=1;
        //visit[j]++;
        dist[n]=0;
        visited[n]=1;
        Queue<Integer> q=new LinkedList<>();
        q.add(n);
        while(!q.isEmpty()){
            int x=q.poll();
            for(int i=0;i<adj[x].size();i++){
                if(visited[adj[x].get(i)]==0){
                    q.add(adj[x].get(i));
                    visited[adj[x].get(i)]=1;
                    dist[adj[x].get(i)]=dist[x]+1;
                }
                if(adj[x].get(i)==m)
                {
                    return;
                }
            }
        }
        // for(int i=0;i<adj[x].size();i++){
        //     if(visited[adj[x].get(i)]==0){
        //         //check[j]++;
        //         ans1++;
        //         dfs(adj[x].get(i));
        //     }
        // }
    } 
    
    public static void main(String args[]){
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter w = new PrintWriter(outputStream);
        int t=in.nextInt(),i,j;
        for(i=0;i<t;i++){
            int n=in.nextInt();
            int arr[]=new int[n];
            int farr[]=new int[200001];
            int flag=-1;
            TreeSet<Integer> tr1=new TreeSet<>();
            TreeSet<Integer> tr2=new TreeSet<>();
            for(j=0;j<n;j++){
                arr[j]=in.nextInt();
                farr[arr[j]]++;
                if(farr[arr[j]]==3){
                    flag=0;
                }
                if(arr[j]==1){
                    
                }
            }
            if(flag==0||farr[1]!=2){
                w.println(0);
                //w.println("here"+farr[1]);
                continue;
            }
            int comp=0,ans=0;
            flag=0;
            for(j=0;j<n;j++){
                if(comp==0){
                    if(tr1.contains(arr[j])){
                        comp=1;
                        //continue;
                    }else{
                        tr1.add(arr[j]);
                    }
                }if(comp==1){
                    if(tr2.contains(arr[j])){
                        flag=-10;
                    }else{
                        tr2.add(arr[j]);
                    }
                }
            }
            // w.println(tr1);
            // w.println(tr2);
            int x1=-1,y1=-1,x2=-1,y2=-1;
            if(flag>-1&&tr1.last()==tr1.size()&&tr2.last()==tr2.size()){
                ans++;
                //w.println("here");
                x1=tr1.size();
                y1=tr2.size();
            }else{
                x1=-1;
                y1=-1;
            }
            TreeSet<Integer> tr3=new TreeSet<>();
            TreeSet<Integer> tr4=new TreeSet<>();
            comp=0;flag=0;
            for(j=n-1;j>=0;j--){
                if(comp==0){
                    if(tr3.contains(arr[j])){
                        comp=1;
                        //continue;
                    }else{
                        tr3.add(arr[j]);
                    }
                }
                if(comp==1){
                    if(tr4.contains(arr[j])){
                        flag=-10;
                    }else{
                        tr4.add(arr[j]);
                    }
                }
            }
            //w.println(tr3+" "+tr4+" "+flag);
            if(flag>-1&&tr3.last()==tr3.size()&&tr4.last()==tr4.size()){
                ans++;
                //w.println("here12");
                y2=tr3.size();
                x2=tr4.size();
            }else{
                x2=-1;
                y2=-1;
            }
            if(ans==2){
                if(x2==x1&&y1==y2&&x1!=-1&&y2!=-1){
                    w.println(1);
                    w.println(x1+" "+y1);
                }else if(x2!=x1&&y2!=y1){
                    w.println(2);
                    w.println(x1+" "+y1);
                    w.println(x2+" "+y2);
                }
            
            }else if(ans==1){
                if(x1!=-1){
                    w.println(1);
                    w.println(x1+" "+y1);
                }else{
                    w.println(1);
                    w.println(x2+" "+y2);
                }
            }else{
                w.println(0);
            }
        }
        
        w.close();
    }
   
}