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

public class QuesD {
 
  public static void main(String[] args) { 
      int t = sc.nextInt();
      while(t-- > 0) 
        solve();
      out.close();
  }

 
  private static void solve() {
	  long n = sc.nextInt();
	  int count=count((int)n);
	  out.println(count);
	  print((int)n);
  }
  static void print(int n) {
	  if(n==3) {
		  out.println(3+" "+2);
		  out.println(3+" "+2);		  
	  }else if(n==4) {
		  out.println(3+" "+4);
		  out.println(4+" "+2);
		  out.println(4+" "+2);
	  }else {
		  int tmp=(int)Math.ceil(Math.sqrt((double)n));
		  for(int i=n-1;i>tmp;i--) {
			  out.println(i+" "+n);
			  
		  }
		  out.println(n+" "+tmp);
		  out.println(n+" "+tmp);
		  print(tmp);
		  
	  }
  }
  static int count(int n) {
	  if(n==3) return 2;
	  if(n==4) return 3;
	  int tmp=(int)Math.ceil(Math.sqrt((double)n));
	  return n-tmp+1+count(tmp);
  }
  
  class UnionFind {
      int[] father;
      int[] sz;
      int count ;
      UnionFind(int n) {
          this.father = new int[n];
          this.sz = new int[n];
          this.count = n;
          for (int i = 0; i < n; i++) {
              father[i] = i;
          }
      }

      public int find(int x) {
          if (x != father[x]) father[x] = find(father[x]);
          return father[x];
      }

      public void union(int x , int y) {
          x = find(x);
          y = find(y);
          
          if (sz[x] < sz[y]) {
              int temp = x;
              x = y;
              y = temp;
          }
          father[y] = x;
          sz[x] += sz[y];
          --count;
          
      }
      
      public boolean connected(int x, int y) {
          return find(x) == find(y);
      }
  }
 
  public static void sort(int[] a) {
    int l = 0, r = a.length;
      ArrayList<Integer> list=new ArrayList<>();
      for (int i=l ; i<r; i++) list.add(a[i]);
      Collections.sort(list);
      for (int i=l; i<r; i++) a[i]=list.get(i-l);
  }
  static long gcd(long a, long b)
  {
      if (b == 0)
          return a;
      return gcd(b, a % b);
  }
  static long lower_Bound(long A[],int low,int high, long x) 
  { 
      if (low > high) 
      if (x >= A[high]) 
          return A[high]; 

      int mid = (low + high) / 2; 
       
      if (A[mid] == x) 
          return A[mid]; 

      if (mid > 0 && A[mid - 1] <= x && x < A[mid]) 
          return A[mid - 1]; 

      if (x < A[mid]) 
          return lower_Bound( A, low, mid - 1, x); 

      return lower_Bound(A, mid + 1, high, x); 
  } 
  static boolean isPrime(long N)
  {
      if (N<=1)  return false; 
      if (N<=3)  return true; 
      if (N%2 == 0 || N%3 == 0) return false; 
      for (int i=5; i*i<=N; i=i+6) 
          if (N%i == 0 || N%(i+2) == 0) 
              return false; 
      return true; 
  }
 
  public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
 
  public static FastScanner sc = new FastScanner();
 
  static class FastScanner {
      BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st=new StringTokenizer("");
      String next() {
        while (!st.hasMoreTokens())
          try {
            st=new StringTokenizer(br.readLine());
          } catch (IOException e) {
            e.printStackTrace();
          }
        return st.nextToken();
      }
      
      int nextInt() {
        return Integer.parseInt(next());
      }
      int[] readArray(int n) {
        int[] a=new int[n];
        for (int i=0; i<n; i++) a[i]=nextInt();
        return a;
      }
      long nextLong() {
        return Long.parseLong(next());
      }
  }
}