Problem: You have an array a_1, a_2, ..., a_n where a_i = i.

In one step, you can choose two indices x and y (x ≠ y) and set a_x = \left⌈ (a_x)/(a_y) \right⌉ (ceiling function).

Your goal is to make array a consist of n - 1 ones and 1 two in no more than n + 5 steps. Note that you don't have to minimize the number of steps.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first and only line of each test case contains the single integer n (3 ≤ n ≤ 2 ⋅ 10^5) — the length of array a.

It's guaranteed that the sum of n over test cases doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print the sequence of operations that will make a as n - 1 ones and 1 two in the following format: firstly, print one integer m (m ≤ n + 5) — the number of operations; next print m pairs of integers x and y (1 ≤ x, y ≤ n; x ≠ y) (x may be greater or less than y) — the indices of the corresponding operation.

It can be proven that for the given constraints it's always possible to find a correct sequence of operations.

Example

Input


2
3
4


Output


2
3 2
3 2
3
3 4
4 2
4 2

Note

In the first test case, you have array a = [1, 2, 3]. For example, you can do the following: 

  1. choose 3, 2: a_3 = \left⌈ (a_3)/(a_2) \right⌉ = 2 and array a = [1, 2, 2]; 
  2. choose 3, 2: a_3 = \left⌈ 2/2 \right⌉ = 1 and array a = [1, 2, 1]. 

You've got array with 2 ones and 1 two in 2 steps.

In the second test case, a = [1, 2, 3, 4]. For example, you can do the following: 

  1. choose 3, 4: a_3 = \left⌈ 3/4 \right⌉ = 1 and array a = [1, 2, 1, 4]; 
  2. choose 4, 2: a_4 = \left⌈ 4/2 \right⌉ = 2 and array a = [1, 2, 1, 2]; 
  3. choose 4, 2: a_4 = \left⌈ 2/2 \right⌉ = 1 and array a = [1, 2, 1, 1]. 

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.InputMismatchException;
public class DEducation101 {

	public static void main(String[] args) {
		FastScanner in = new FastScanner(System.in);
		
		int T = in.nextInt();
		StringBuilder sb = new StringBuilder();
		
		while(T --> 0) {
			int N = in.nextInt();
			
			ArrayList<Integer> a = new ArrayList<>();
			ArrayList<Integer> b = new ArrayList<>();
			
			fill(N, a, b);
			
			sb.append(a.size());
			sb.append("\n");
			
			for(int i = 0; i < a.size(); i++) {
				sb.append(a.get(i) + " " + b.get(i) + "\n");
			}
		}
		
		System.out.println(sb);

	}
	
	public static void fill(int N, ArrayList<Integer> first, ArrayList<Integer> second) {
		if(N == 3) {
			/*
			 3 2
3 2
3
3 4
4 2
4 2
			 */
			
			first.add(3);
			second.add(2);
			first.add(3);
			second.add(2);
			
			return;
		}
		
		if(N == 4) {
			first.add(3);
			second.add(4);
			first.add(4);
			second.add(2);
			first.add(4);
			second.add(2);
			
			return;
		}
		
		int sqrt = (int) Math.ceil(Math.sqrt(N));
		
		for(int i = sqrt + 1; i < N; i++) {
			first.add(i);
			second.add(N);
		}
		
		first.add(N);
		second.add(sqrt);
		first.add(N);
		second.add(sqrt);
		
		fill(sqrt, first, second);
	}
	
	/**
	 * Source: Matt Fontaine
	 */
	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int chars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
		}

		int read() {
			if (chars == -1)
				throw new InputMismatchException();
			if (curChar >= chars) {
				curChar = 0;
				try {
					chars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (chars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

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

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String next() {
			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 String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}
/*
2
3
4
outputCopy
2
3 2
3 2
3
3 4
4 2
4 2
*/