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

public class Main {

	static long sx = 0, sy = 0, mod = (long) (1e9 + 7);

	static ArrayList<Integer>[] a;
	static long[][][] dp;
	static int[] size;
	static long[] farr;
	public static PrintWriter out;
	static ArrayList<pair> pa = new ArrayList<>();
	static long[] fact = new long[(int) 1e6];
	static boolean b = false;
	static StringBuilder sb = new StringBuilder();
	static boolean cycle = false;
	// static long m = 998244353;
	static long[] no, col;
	static String s;
	static int k = 0, n = 0, m = 0;
	static int[] c;
	static long ans = 0;
	static long[][] p;
	static HashMap<Integer, Integer> hm;

	public static void main(String[] args) throws IOException {

		Scanner scn = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

		out = new PrintWriter(System.out);
		// Reader scn = new Reader();

		int t = scn.nextInt();

		while (t-- != 0) {

			int n = scn.nextInt();

			int[] a = new int[n + 1];

			for (int i = 1; i <= n; i++)
				a[i] = scn.nextInt();

			int[] lmin = new int[n + 1];
			int[] lmax = new int[n + 1];
			int[] rmin = new int[n + 1];
			int[] rmax = new int[n + 1];

			boolean[] b1 = new boolean[n + 1];
			Arrays.fill(b1, true);
			boolean[] b2 = new boolean[n + 1];
			Arrays.fill(b2, true);
			HashSet<Integer> hm = new HashSet<>();

			lmin[1] = lmax[1] = a[1];

			rmin[n] = rmax[n] = a[n];

			hm.add(a[1]);

			for (int i = 2; i <= n; i++) {

				if (hm.contains(a[i]))
					b1[i] = false;

				b1[i] &= b1[i - 1];

				lmin[i] = Math.min(a[i], lmin[i - 1]);
				lmax[i] = Math.max(a[i], lmax[i - 1]);

				hm.add(a[i]);
			}

			hm = new HashSet<>();
			hm.add(a[n]);

			for (int i = n - 1; i >= 1; i--) {

				if (hm.contains(a[i]))
					b2[i] = false;

				b2[i] &= b2[i + 1];

				rmin[i] = Math.min(rmin[i + 1], a[i]);
				rmax[i] = Math.max(rmax[i + 1], a[i]);

				hm.add(a[i]);
			}

			int ans = 0;

			StringBuilder sb = new StringBuilder();

			for (int i = 1; i <= n - 1; i++) {

				if (lmin[i] == 1 && lmax[i] == i && rmin[i + 1] == 1 && rmax[i + 1] == n - i && b1[i] && b2[i+1]) {
					ans++;
					sb.append(i + " " + (n - i));
					sb.append("\n");
				}

				hm.add(a[i]);
			}

			System.out.println(ans);
			System.out.print(sb);

		}
	}

	// _________________________TEMPLATE_____________________________________________________________

	// public static long lcm(long x, long y) {
	//
	// return (x * y) / gcd(x, y);
	// }
	//
	// private static long gcd(long x, long y) {
	// if (x == 0)
	// return y;
	//
	// return gcd(y % x, x);
	// }

	// static class comp implements Comparator<Integer> {
	//
	// @Override
	// public int compare(Integer o1, Integer o2) {
	// return depth[o2] - depth[o1];
	// }
	//
	// }

	// public static long pow(long a, long b) {
	//
	// if (b < 0)
	// return 0;
	// if (b == 0 || b == 1)
	// return (long) Math.pow(a, b);
	//
	// if (b % 2 == 0) {
	//
	// long ret = pow(a, b / 2);
	// ret = (ret % mod * ret % mod) % mod;
	// return ret;
	// }
	//
	// else {
	// return ((pow(a, b - 1) % mod) * a % mod) % mod;
	// }
	// }

	private static class pair implements Comparable<pair> {

		int w, h;
		int idx;

		pair(int a, int b, int i) {

			w = a;
			h = b;
			idx = i;
		}

		@Override
		public int compareTo(pair o) {

			if (this.w != o.w)
				return this.w - o.w;

			else
				return this.h - o.h;
		}

	}

	private static String reverse(String s) {

		return new StringBuilder(s).reverse().toString();
	}

	public static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[1000000 + 1]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}

		public int[] nextIntArray(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) throws IOException {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextLong();
			}
			return arr;
		}

		public int[][] nextInt2DArray(int m, int n) throws IOException {
			int[][] arr = new int[m][n];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++)
					arr[i][j] = nextInt();
			}
			return arr;
		}

		public long[][] nextInt2DArrayL(int m, int n) throws IOException {
			long[][] arr = new long[m][n];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++)
					arr[i][j] = nextInt();
			}
			return arr;
		}
		// kickstart - Solution
		// atcoder - Main
	}

}