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:
//samajh sako to samajh lo
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class Main extends PrintWriter {
    static BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
    Main () { super(System.out); }
    public static void main(String[] args) throws IOException{
        Main  d1=new Main   ();d1.main();d1.flush();
    }
    void main() throws IOException {
        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        PrintWriter out = new PrintWriter(System.out);
        int t = 1;
        t = i(s()[0]);
        while (t-- > 0) {
            String[] s1=s();
             int n=i(s1[0]);
             if(n>16){
            sb.append(n+5+"\n");
            for(int i=n-1;i>2;i--){
                if(i==16) continue;
                sb.append((i)+" "+(n)+"\n");
            }
            sb.append(n+" "+16+"\n");
            sb.append(n+" "+16+"\n");
            sb.append(n+" "+16+"\n");
            sb.append(n+" "+16+"\n");
            sb.append(n+" "+16+"\n");
            sb.append(16+" "+2+"\n");
            sb.append(16+" "+2+"\n");
            sb.append(16+" "+2+"\n");
            sb.append(16+" "+2+"\n");}
            else{
                 sb.append(n+5+"\n");
                 for(int i=n-1;i>2;i--){
                     sb.append((i)+" "+(n)+"\n");
                 }
                 sb.append(n+" "+2+"\n");
                 sb.append(n+" "+2+"\n");
                 sb.append(n+" "+2+"\n");
                 sb.append(n+" "+2+"\n");
                 sb.append(n+" "+2+"\n");
                 sb.append(n+" "+2+"\n");
                 sb.append(n+" "+2+"\n");
                 sb.append(n+" "+2+"\n");
              
              }
        }
        System.out.println(sb);

        }static StringBuffer ans;static int[][] vis;static int[][] px,py;
    public static void dfs(char[][] a,int i,int j) {
        Queue<Integer> qx = new LinkedList<>();
        Queue<Integer> qy = new LinkedList<>();
        Queue<StringBuffer> qz = new LinkedList<>();
        qx.add(i);
        qy.add(j);
        qz.add(new StringBuffer(""));

        while (!qx.isEmpty()) {
            int x = qx.poll();
            int y = qy.poll();

            vis[x][y] = 1;
          //  StringBuffer sb = qz.poll();
            if (a[x][y] == 'A') {
                while(px[x][y]!=-1) {
                    int nx = px[x][y];
                    int ny = py[x][y];
//                    System.out.println(nx + " " + ny + " " + px[nx][ny] + " " + a[x][y]);
                    if (nx < x) {
                        ans.append("U");
                    }
                    if (nx > x) {
                        ans.append("D");
                    }
                    if (ny > y) {
                        ans.append("R");
                    }
                    if (ny < y)
                        ans.append("L");
                    x = nx;
                    y = ny;
                }return ;
            }
//            System.out.println();
            if (x - 1 >= 0 && a[x - 1][y] != '#' && vis[x - 1][y] == 0) {
                px[x-1][y]=x;py[x-1][y]=y;
                vis[x-1][y]=1;
                qx.add(x - 1);
                qy.add(y);

            }
            if (x + 1<a.length && a[x + 1][y] != '#' && vis[x + 1][y] == 0) {
             qx.add(x + 1);vis[x+1][y]=1;
                px[x+1][y]=x;py[x+1][y]=y;
                qy.add(y);

            }
            if (y + 1 < a[0].length && a[x][y + 1] != '#' && vis[x][y + 1] == 0) {
                qx.add(x);vis[x][y+1]=1;
                px[x][y+1]=x;py[x][y+1]=y;
                qy.add(y + 1);
            }
            if (y - 1 >= 0 && a[x][y - 1] != '#' && vis[x][y - 1] == 0) {
                qx.add(x);vis[x][y-1]=1;
                px[x][y-1]=x;py[x][y-1]=y;
                qy.add(y - 1);
            }

        }
    }
    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    static int[][] d={{-1,0},{1,0},{0,-1},{0,1}};
    static boolean wb(int i,int j,int n,int m){
        if(i>=0&&i<n&&j>=0&&j<m) return true;
        return false;
    }
    static String[] s() throws IOException {
        return s.readLine().trim().split("\\s+");
    }
    static int i(String ss) {
        return Integer.parseInt(ss);
    }
    static long l(String ss) {
        return Long.parseLong(ss);
    }
    public void arr(long[] a,int n) throws IOException {
        //        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        String[] s2=s();
        for(int i=0;i<n;i++){
            a[i]=l(s2[i]);
        }
    }
    public void arri(int[] a,int n) throws IOException{
        //        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        String[] s2=s();
        for(int i=0;i<n;i++){
            a[i]=i(s2[i]);
        }
    }
    public void sort(long[] a,int l,int h){
        if(l==h) return;
        int mid=(l+h)/2;

        sort(a,l,mid);
        sort(a,mid+1,h);
        merge(a,l,(l+h)/2,h);
    }
    void merge(long arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        long L[] = new long[n1];
        long R[] = new long[n2];
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}
class Pair {
    int  a,b,c;
    public Pair(int  a,int b){
        this.a=a;this.b=b;this.c=c;}
}class Sortbyroll implements Comparator<Pair> {
    public int compare(Pair a, Pair b){
        return a.a-b.a;
    }}
class Sortbyroll1 implements Comparator<Pair> {
    public int compare(Pair a, Pair b){
        return a.b-b.b;
    }}