K. One Line
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Construct a set of at least $$$m=\left\lfloor \sqrt{2}n \right\rfloor$$$ points, where the coordinates of the $$$i$$$-th point are $$$(x_i,y_i)$$$, such that:

  • $$$x_i,y_i \in [1,n]\cap \mathbb{Z}$$$ for all $$$1 \le i \le m$$$.
  • $$$x_i \ne x_j$$$ or $$$y_i \ne y_j$$$ for all $$$1 \le i \lt j \le m$$$.
  • No three distinct points are collinear.

It can be shown that this is always possible.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 138$$$). The description of the test cases follows.

The only line of each test case contains an integer $$$n$$$ ($$$3 \le n \le 5000$$$). It is guaranteed that within the same test, the values of $$$n$$$ in all test cases are pairwise distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.

Output

For each test case, first output an integer $$$m$$$ ($$$\left\lfloor \sqrt{2}n \right\rfloor \le m \le n^2$$$), representing the number of points you constructed. Then output $$$m$$$ lines, where the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i,y_i \le n$$$), representing the coordinates of the $$$i$$$-th point.

Example
Input
1
3
Output
4
1 1
2 1
2 2
3 2