#include <bits/stdc++.h>
#pragma gcc optimize("ofast")
using namespace std;
long long modexp(long long a, long long b, long long m) {
  long long r = 1;
  a = a % m;
  while (b > 0) {
    if (b & 1) r = (r * a) % m;
    b = b / 2;
    a = (a * a) % m;
  }
  return r % m;
}
int main() {
  ios_base::sync_with_stdio(0);
  long long t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    set<long long, greater<long long>> evens, odds;
    for (int i = 1; i < n + 1; i++) {
      if (i % 2 == 1)
        odds.insert(i);
      else
        evens.insert(i);
    }
    long long mn = 0;
    long long a, b, guy;
    vector<pair<long long, long long>> moves;
    if (n % 2 == 0) {
      while (odds.size() >= 2 || evens.size() >= 2) {
        if (evens.size() >= 2) {
          a = *evens.begin();
          b = *(next(evens.begin(), 1));
          evens.erase(a);
          evens.erase(b);
          moves.push_back(make_pair(a, b));
          guy = ceil(((double)a + (double)b) / (double)2);
          if (guy % 2 == 1) {
            if (odds.find(guy) != odds.end())
              moves.push_back(make_pair(guy, guy));
            odds.insert(guy);
          } else
            evens.insert(guy);
        }
        if (odds.size() >= 2) {
          a = *odds.begin();
          b = *(next(odds.begin(), 1));
          odds.erase(a);
          odds.erase(b);
          moves.push_back(make_pair(a, b));
          guy = ceil(((double)a + (double)b) / (double)2);
          if (guy % 2 == 1)
            odds.insert(guy);
          else {
            if (evens.find(guy) != evens.end())
              moves.push_back(make_pair(guy, guy));
            evens.insert(guy);
          }
        }
      }
      long long oddsz = odds.size();
      long long evensz = evens.size();
      if (oddsz == 0)
        cout << *evens.begin() << '\n';
      else if (evensz == 0) {
        cout << *odds.begin() << '\n';
      } else {
        long long a = *odds.begin();
        long long b = *(evens.begin());
        moves.push_back(make_pair(a, b));
        cout << ceil(((double)a + (double)b) / (double)2) << '\n';
      }
      for (auto j : moves) {
        cout << j.first << ' ' << j.second << '\n';
      }
    } else {
      while (odds.size() >= 2 || evens.size() >= 2) {
        if (odds.size() >= 2) {
          a = *odds.begin();
          b = *(next(odds.begin(), 1));
          odds.erase(a);
          odds.erase(b);
          moves.push_back(make_pair(a, b));
          guy = ceil(((double)a + (double)b) / (double)2);
          if (guy % 2 == 1)
            odds.insert(guy);
          else {
            if (evens.find(guy) != evens.end())
              moves.push_back(make_pair(guy, guy));
            evens.insert(guy);
          }
        }
        if (evens.size() >= 2) {
          a = *evens.begin();
          b = *(next(evens.begin(), 1));
          evens.erase(a);
          evens.erase(b);
          moves.push_back(make_pair(a, b));
          guy = ceil(((double)a + (double)b) / (double)2);
          if (guy % 2 == 1) {
            if (odds.find(guy) != odds.end())
              moves.push_back(make_pair(guy, guy));
            odds.insert(guy);
          } else
            evens.insert(guy);
        }
      }
      long long oddsz = odds.size();
      long long evensz = evens.size();
      if (oddsz == 0)
        cout << *evens.begin() << '\n';
      else if (evensz == 0) {
        cout << *odds.begin() << '\n';
      } else {
        long long a = *odds.begin();
        long long b = *(evens.begin());
        moves.push_back(make_pair(a, b));
        cout << ceil(((double)a + (double)b) / (double)2) << '\n';
      }
      for (auto j : moves) {
        cout << j.first << ' ' << j.second << '\n';
      }
    }
  }
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
#pragma gcc optimize("ofast")
using namespace std;
long long modexp(long long a, long long b, long long m) {
  long long r = 1;
  a = a % m;
  while (b > 0) {
    if (b & 1) r = (r * a) % m;
    b = b / 2;
    a = (a * a) % m;
  }
  return r % m;
}
int main() {
  ios_base::sync_with_stdio(0);
  long long t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    set<long long, greater<long long>> evens, odds;
    for (int i = 1; i < n + 1; i++) {
      if (i % 2 == 1)
        odds.insert(i);
      else
        evens.insert(i);
    }
    long long mn = 0;
    long long a, b, guy;
    vector<pair<long long, long long>> moves;
    if (n % 2 == 0) {
      while (odds.size() >= 2 || evens.size() >= 2) {
        if (evens.size() >= 2) {
          a = *evens.begin();
          b = *(next(evens.begin(), 1));
          evens.erase(a);
          evens.erase(b);
          moves.push_back(make_pair(a, b));
          guy = ceil(((double)a + (double)b) / (double)2);
          if (guy % 2 == 1) {
            if (odds.find(guy) != odds.end())
              moves.push_back(make_pair(guy, guy));
            odds.insert(guy);
          } else
            evens.insert(guy);
        }
        if (odds.size() >= 2) {
          a = *odds.begin();
          b = *(next(odds.begin(), 1));
          odds.erase(a);
          odds.erase(b);
          moves.push_back(make_pair(a, b));
          guy = ceil(((double)a + (double)b) / (double)2);
          if (guy % 2 == 1)
            odds.insert(guy);
          else {
            if (evens.find(guy) != evens.end())
              moves.push_back(make_pair(guy, guy));
            evens.insert(guy);
          }
        }
      }
      long long oddsz = odds.size();
      long long evensz = evens.size();
      if (oddsz == 0)
        cout << *evens.begin() << '\n';
      else if (evensz == 0) {
        cout << *odds.begin() << '\n';
      } else {
        long long a = *odds.begin();
        long long b = *(evens.begin());
        moves.push_back(make_pair(a, b));
        cout << ceil(((double)a + (double)b) / (double)2) << '\n';
      }
      for (auto j : moves) {
        cout << j.first << ' ' << j.second << '\n';
      }
    } else {
      while (odds.size() >= 2 || evens.size() >= 2) {
        if (odds.size() >= 2) {
          a = *odds.begin();
          b = *(next(odds.begin(), 1));
          odds.erase(a);
          odds.erase(b);
          moves.push_back(make_pair(a, b));
          guy = ceil(((double)a + (double)b) / (double)2);
          if (guy % 2 == 1)
            odds.insert(guy);
          else {
            if (evens.find(guy) != evens.end())
              moves.push_back(make_pair(guy, guy));
            evens.insert(guy);
          }
        }
        if (evens.size() >= 2) {
          a = *evens.begin();
          b = *(next(evens.begin(), 1));
          evens.erase(a);
          evens.erase(b);
          moves.push_back(make_pair(a, b));
          guy = ceil(((double)a + (double)b) / (double)2);
          if (guy % 2 == 1) {
            if (odds.find(guy) != odds.end())
              moves.push_back(make_pair(guy, guy));
            odds.insert(guy);
          } else
            evens.insert(guy);
        }
      }
      long long oddsz = odds.size();
      long long evensz = evens.size();
      if (oddsz == 0)
        cout << *evens.begin() << '\n';
      else if (evensz == 0) {
        cout << *odds.begin() << '\n';
      } else {
        long long a = *odds.begin();
        long long b = *(evens.begin());
        moves.push_back(make_pair(a, b));
        cout << ceil(((double)a + (double)b) / (double)2) << '\n';
      }
      for (auto j : moves) {
        cout << j.first << ' ' << j.second << '\n';
      }
    }
  }
  return 0;
}

```