题目描述

给定一个整数 $k$，请在平面直角坐标系中放置 $0 \le n \le 500$ 个法杖。每个法杖必须位于互不相同的整点坐标上。

对于两个点 $a=(x_a,y_a)$ 与 $b=(x_b,y_b)$，定义

以及

你需要构造这些点，使得恰好有 $k$ 对下标 $(i,j)$ 满足 $1 \le i < j \le n$ 且 $\rho(i,j)=d(i,j)$。

可以证明，在本题限制内总能构造出答案。如果有多种答案，输出任意一种。

输入格式

第一行包含一个整数 $t$，表示测试用例数量。

接下来 $t$ 行，每行包含一个整数 $k$。

输出格式

对于每个测试用例，第一行输出一个整数 $n$，表示放置的法杖数量。

接下来输出 $n$ 行，每行输出两个整数 $x_i,y_i$，表示第 $i$ 个法杖的坐标。

所有输出点必须互不相同，并且坐标需要满足 $-10^9 \le x_i,y_i \le 10^9$。

数据范围

• $1 \le t \le 1000$
• $0 \le k \le 10^5$
• $0 \le n \le 500$
• $-10^9 \le x_i,y_i \le 10^9$

样例输入

3
0
2
5

样例输出

0
4
0 0
1 0
2 1000000
3 1000000
7
0 0
1 0
2 0
3 1000000
4 1000000
5 2000000
6 2000000

提示

两个不同点满足 $\rho=d$，当且仅当它们的横坐标相同或纵坐标相同。

来源：Codeforces 2072E。