Numbers 1, 2, 3, ... n (each integer from 1 to n once) are written on a board. In one operation you can erase any two numbers a and b from the board and write one integer (a + b)/(2) rounded up instead.

You should perform the given operation n - 1 times and make the resulting number that will be left on the board as small as possible. 

For example, if n = 4, the following course of action is optimal:

  1. choose a = 4 and b = 2, so the new number is 3, and the whiteboard contains [1, 3, 3]; 
  2. choose a = 3 and b = 3, so the new number is 3, and the whiteboard contains [1, 3]; 
  3. choose a = 1 and b = 3, so the new number is 2, and the whiteboard contains [2]. 



It's easy to see that after n - 1 operations, there will be left only one number. Your goal is to minimize it.

Input

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

The only line of each test case contains one integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the number of integers written on the board initially.

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

Output

For each test case, in the first line, print the minimum possible number left on the board after n - 1 operations. Each of the next n - 1 lines should contain two integers — numbers a and b chosen and erased in each operation.

Example

Input


1
4


Output


2
2 4
3 3
3 1
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class contest11103{
	static Scanner scan = new Scanner(System.in);
	static long ceil(long x, long y){
		if((x+y)%2==0){
			return (x+y)/2;
		}else{
			return (x+y)/2+(long)1;
		}
	}
	static int t = scan.nextInt();
	public static void main(String[] args){
		for(int i=0; i<t; i++){
			int n = scan.nextInt();
			System.out.println(2);
			if(n==2){
				System.out.println(1+" "+2);
				continue;
			}
			System.out.println(n+" "+(n-2));
			System.out.println((n-1)+" "+(n-1));
			for(int j=0; j<n-3; j++){
				int x = n-1-j;
				int y = n-3-j;
				System.out.println(x+" "+y);
			}
		}
	}
}