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.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
 
 
import java.util.*;
 
public class template {
 
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	static int countBits(long n) 
    { 
        int count = 0; 
        while (n != 0) 
        { 
            count++; 
            n >>= 1; 
        } 
        return count; 
    } 
	
	void solve() {
		int t = ni();
		
		while(t-- > 0) {
			int n = ni();
			int a[] = na(n);
			
			HashSet<Integer> hs = new HashSet<>();
			int max = 0;
			int lp[] = new int[n];
			int rp[] = new int[n];
			
			for(int i = 0 ; i<n ; i++) {
				if(!hs.contains(a[i])) {
					hs.add(a[i]);
					max = Math.max(max, a[i]);
					lp[i] = max;
				}
				else {
					while(i<n) {
						lp[i] = -1;
						i++;
					}
				}
			}
			
			max = 0;
			hs = new HashSet<>();
			for(int i = n-1 ; i>=0 ; i--) {
				if(!hs.contains(a[i])) {
					hs.add(a[i]);
					max = Math.max(max, a[i]);
					rp[i] = max;
				}
				else {
					while(i>=0) {
						rp[i] = -1;
						i--;
					}
				}
			}
			int c = 0;
			for(int i = 0 ; i<n-1 ; i++) {
				if(lp[i] == i+1 && rp[i+1] == n-i-1) c++;
			}
			out.println(c);
			for(int i = 0 ; i<n-1 ; i++) {
				if(lp[i] == i+1 && rp[i+1] == n-i-1) 
					out.println(lp[i]+" "+rp[i+1]);
			}
			
		}	
		
	}
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
 
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
		//tr(System.currentTimeMillis()-s+"ms");
	}
 
	public static void main(String[] args) throws Exception { new template().run(); }
	
	private void sort(int[] arr, int start, int end){
        if(start >= end) return;
        int mid = start + (end - start) / 2;
        sort(arr, start, mid);
        sort(arr, mid +1, end);
        merge(arr, start, mid, end);
    }
	private void merge(int[] arr, int start, int mid, int end){
        int i = start, j = mid + 1;
        int[] help = new int[end - start + 1];
        int c = 0;
        while(i <= mid && j <= end){
            help[c++] = arr[j] < arr[i] ? arr[j++] : arr[i++];
        }
        while(i <= mid){
            help[c++] = arr[i++];
        }
        while(j <= end){
            help[c++] = arr[j++];
        }
        for(int k = 0; k < help.length; k++){
            arr[start + k] = help[k];
        }
    }
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
 
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
 
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
 
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
 
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
 
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
 
	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
 
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
 
	private int[][] na(int n , int m)
	{
		int[][] a = new int[n][m];
		for(int i = 0;i < n;i++) 
			for(int j = 0 ; j<m ; j++) a[i][j] = ni();
		return a;
	}
 
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
 
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
 
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
 
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
 
	void display2D(int a[][]) {
		for(int i[] : a) {
			for(int j : i) {
				out.print(j+" ");
			}
			out.println();
		}
	}
 
	int[][] creategraph(int n , int m) {
		int g[][] = new int[n+1][];
 
		int from[] = new int[m];
		int to[] = new int[m];
		int ct[] = new int[n+1];
 
		for(int i = 0 ; i<m; i++) {
			from[i] = ni();
			to[i] = ni();
			ct[from[i]]++;
			ct[to[i]]++;
		}
 
		int parent[] = new int[n+1];
 
		for(int i = 0 ; i<n+1 ; i++) g[i] = new int[ct[i]];
 
		for(int i = 0 ; i<m ; i++) {
			g[from[i]][--ct[from[i]]] = to[i];
			g[to[i]][--ct[to[i]]] = from[i];
		}
 
		return g;
	}
 
	static long __gcd(long a, long b)
	{
 
		if(b == 0) 
		{
			return a;
		}
		else
		{
			return __gcd(b, a % b);
		}
	}
 
	// To compute x^y under modulo m
	static long power(long x, long y, long p)
	{
 
		// Initialize result
		long res = 1;
 
		// Update x if it is more than or
		// equal to p
		x = x % p;
 
		while (y > 0)
		{
 
			// If y is odd, multiply x
			// with result
			if (y % 2 == 1)
				res = (res * x) % p;
 
			// y must be even now
			y = y >> 1; // y = y/2
		x = (x * x) % p;
		}
 
		return res;
	}
 
	// Function to find modular 
	// inverse of a under modulo m
	// Assumption: m is prime
	static long modInverse(long a, int m)
	{
		if (__gcd(a, m) != 1) {
			//System.out.print("Inverse doesn't exist");
			return -1;
		}
 
		else {
 
			// If a and m are relatively prime, then
			// modulo inverse is a^(m-2) mode m
			//			System.out.println("Modular multiplicative inverse is "
			//											+power(a, m - 2, m));
			return power(a, m - 2, m);
		}
	}
 
	static long nCrModPFermat(int n, int r,
			int p , long fac[])
	{
 
		// Base case
		if (r == 0)
			return 1;
 
		// Fill factorial array so that we
		// can find all factorial of r, n
		// and n-r
		long t = (fac[n]* modInverse(fac[r], p))%p;
 
		return ( (t* modInverse(fac[n-r], p))% p);
	}
 
 
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}