思路

递归，假设我们要处理 $[1, x]$。如果 $x = 2$，则不需要处理。否则，找到满足 $y \ge \lceil \frac{x}{y} \rceil$ 的最小 $y$。考虑如何寻找这个 $y$，可以发现 $y$ 越大，不等式越有可能成立。若 $y < \sqrt x$，则 $y < \sqrt x \le \lceil \sqrt x \rceil \le \lceil \frac{x}{y} \rceil$，因此可从 $\lfloor \sqrt x \rfloor - 1$ 开始枚举 $y$。

现在，通过除以一次 $x$ 让 $[y + 1, x)$ 都等于 $1$，再让 $x$ 除以两次 $y$ 使它变成 $1$（当 $\sqrt x$ 为整数时，显然成立。否则，第二次除法，分子小于等于分母），总共 $x - y + 1$ 步操作，即比区间长度多一。最后，递归解决 $[1, y]$。

我们总共会花费 $n - 2 + \textit{num_of_segs}$ 步操作（每一段多一次，$[1, 2]$ 不用操作），其中 $\textit{num_of_segs}$ 是段数。由于它们形如 $(\sqrt x, x], (\sqrt {\sqrt x}, \sqrt x], \cdots$，因此最多有 $log(logn)$ 段。当 $n \le 2^{32}$ 时，最多需要 $n + 3$ 步。

补充：假设段数为 $x$，即对 $n$ 反复开方 $x$ 次可以使 $n$ 变成 $2$。反之，对 $2$ 反复平方 $x$ 次可以使 $2$ 变成 $n$。因此 $2^{2^x} = n$，解得 $x = log_2(log_2n)$。

时间复杂度 $O(n)$。

#include <iostream>
#include <vector>
#include <cmath>

#define endl "\n"

using namespace std;
using PII = pair<int, int>;

void calc(int n, vector<PII> &ans) {
  if (n == 2) return;

  int y = max(1, (int)sqrt(n) - 1);
  while (y < (n + y - 1) / y) y++;

  for (int i = y + 1; i < n; i++) ans.push_back({i, n});
  ans.push_back({n, y});
  ans.push_back({n, y});

  calc(y, ans);
}

void solve() {
  int n;
  cin >> n;
  vector<PII> ans;
  calc(n, ans);

  cout << ans.size() << endl;
  for (auto p : ans) cout << p.first << " " << p.second << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}