信仰是为转瞬即逝的人们而存在
— 信仰之山
山上,早苗凝视着星空。信仰,对于她来说,是风雨交汇、选择分歧的地方,也是四方交汇的地方。为了圣十字的荣耀,让我们一起追寻信仰的标志。
平面上有 $$$n$$$ 个不同的整数点,其中第 $$$i$$$ 个点位于 $$$(x_i,y_i)$$$。要为点着色,请选择两个整数 $$$k_1$$$ 和 $$$k_2$$$,使得由线 $$$x=k_1+0.5$$$ 和 $$$y=k_2+0.5$$$ 划分的四个区域中的每一个都包含 至少一分。每个点 $$$(x,y)$$$ 根据其所在区域进行着色:
- 左上角($$$x\leq k_1$$$ 和 $$$y \gt k_2$$$):该点为红色。
- 右上角($$$x \gt k_1$$$ 和 $$$y \gt k_2$$$):该点呈绿色。
- 左下角($$$x\leq k_1$$$ 和 $$$y\leq k_2$$$):该点为蓝色。
- 右下角($$$x \gt k_1$$$ 和 $$$y\leq k_2$$$):该点为黄色。
第三个测试用例的有效着色,其中 $$$k_1=4$$$ 和 $$$k_2=5$$$。 找出不同颜色的数量,其中当且仅当存在至少一个颜色不同的点时,两种颜色才被认为是不同的, 无论选择 $$$k_1$$$ 和 $$$k_2$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$4 \leq n \leq 2 \cdot 10^6$$$)。
下面的 $$$n$$$ 行每行包含两个整数 $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$),代表第 $$$i$$$ 个点的坐标。
保证每个测试用例中的点都是成对不同的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^6$$$。
输出
对于每个测试用例,输出不同颜色的数量。
示例
输入复制
541 12 23 34 441 44 11 14 487 25 72 71 36 73 67 51 686 13 61 41 14 25 53 44 165 55 43 51 55 32 2
输出复制
011284
注意
在第一个测试用例中,不存在有效的交叉。
在第二个测试用例中,选择 $$$x = y = 2$$$ 会产生有效的着色。可以证明这种颜色是独一无二的。
在第三个测试用例中,图例中显示了有效的颜色。