← 返回题目列表

Codeforces · 2072/E

E. 你喜欢你的英雄和他的两击多目标攻击吗?

中文机器翻译题面 查看原题

明人决定研究一种新的强大咒语。既然拥有不可估量的力量,当然需要大量的空间和精心的准备。为此,明人走进了现场。让我们将场表示为笛卡尔坐标系。

对于该咒语,Akito 需要将 $$$0 \le n \le 500$$$ 法杖放置在 不同的整数坐标 在现场,这样就会有 正好 $$$k$$$ 对 $$$(i, j)$$$ 使得 $$$1 \le i \lt j \le n$$$ 和 $$$\rho(i, j) = d(i, j)$$$。

这里,对于具有整数坐标的两个点 $$$a = (x_a, y_a)$$$ 和 $$$b = (x_b, y_b)$$$, $$$\rho(a, b) = \sqrt{(x_a - x_b)^2 + (y_a - y_b)^2}$$$ 和 $$$d(a, b) = |x_a -x_b| + |y_a - y_b|$$$。

输入

输入的第一行包含一个数字 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

在每个测试用例的唯一行中,有一个数字 $$$k$$$ ($$$0 \le k \le 10^5$$$) — 等式 $$$\rho(i, j) = d(i, j)$$$ 必须成立的人员对的数量。

输出

对于每个测试用例,输出的第一行应打印数字 $$$n$$$ ($$$0 \le n \le 500$$$) — 放置的人员数量。

在以下 $$$n$$$ 行中,成对 整数 $$$x_i, y_i$$$ $$$(-10^9 \le x_i, y_i \le 10^9)$$$ 应该被打印 — 第 $$$i$$$ 员工的坐标。员工的立场必须明确。

示例

输入
复制

3
0
2
5

输出
复制

6
69 52
4 20
789 9308706
1337 1337
-1234 -5678
23456178 707
10
-236 -346262358
273568 6435267
2365437 31441367
246574 -45642372
-236 56
4743623 -192892 
10408080 -8173135
-237415357 31441367
-78125638 278
56 143231
5
1 1
2 1
1 5
3 5
1 10