您和您的朋友住在 $$$n$$$ 的房子里。每栋房子都位于二维平面上的一个具有整数坐标的点上。同一地点可能有不同的房屋。该市市长正在向您询问东部展览馆的建设场地。您必须找到地点的数量(具有整数坐标的点),以便所有房屋到展览的总距离最小。展览可以和一些房子建在同一地点。两点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的距离为 $$$|x_1 - x_2| + |y_1 - y_2|$$$,其中 $$$|x|$$$ 是 $$$x$$$ 的绝对值。
输入
第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 1000)$$$。接下来的 $$$n$$$ 行描述了房屋 $$$(x_i, y_i)$$$ $$$(0 \leq x_i, y_i \leq 10^9)$$$ 的位置。
保证所有$$$n$$$的总和不超过$$$1000$$$。
输出
为每个测试用例输出一个整数 - 展览的不同位置的数量。展览可以和一些房子建在同一地点。
示例
输入 #1
6 3 0 0 2 0 1 2 4 1 0 0 2 2 3 3 1 4 0 0 0 1 1 0 1 1 2 0 0 1 1 2 0 0 2 0 2 0 0 0 0
输出 #1
1 4 4 4 3 1
注意
以下是示例测试用例的图像。蓝点代表房屋,绿色代表展览的可能位置。
第一个测试用例。
第二个测试用例。
第三个测试用例。
第四个测试用例。
第五个测试用例。
第六个测试用例。这里两栋房子都位于$$$(0, 0)$$$。