解题思路

设驿站建在点 $(a,b)$，每天都要从 $(a,b)$ 走到原点 $(0,0)$，并且只能走最短路。

曼哈顿最短路长度为：

$|a|+|b|$

一条从 $(a,b)$ 到 $(0,0)$ 的最短路，本质上只能让 $x$ 坐标一步步向 $0$ 靠近，同时让 $y$ 坐标一步步向 $0$ 靠近，中途不能“走反方向”。

题目内容

在一张无限的二维网格上，有若干住户的家位于整数坐标点上（同一坐标可能有多人）。你首先在任意整数坐标点上固定建造一个快递驿站，然后每天从该驿站出发前往原点$(0,0)$。你总会选择一条从驿站到原点的最短路径。路径由一系列相邻的格点组成，每一步只能向上、下、左、右移动一个单位，路径中包含起点（驿站位置）和终点（原点）。例如：从$(x_0,y_0)$到$(0,0)$的最短路径长度为$|x_0-0|+|y_0-0|$的路径都视为最短路径。你可以在所有最短路径中任选其一。

在选定最优驿站位置后，允许在多天内每天任选一条最短路径并在路径途经的住户完成投递。问最多能累计送达多少不同住户？

输入描述

输入包含多组测试数据。第一行包含整数$T\ (1 \le T \le 10^5)$表示测试组数。每组数据描述如下：

• 第一行输入一个整数$n\ (1 \le n \le 2 \times 10^5)$；
• 接下来$n$行，每行输入两个整数$x_i, y_i\ (-10^9 \le x_i, y_i \le 10^9)$，表示一位住户的家在$(x_i,y_i)$。

保证所有测试中 $n$ 的总和不超过 $2× 10^5$。

输出描述

对于每组测试数据，输出一行，仅包含一个整数——在最优驿站位置与任意多次最短路径选择下，最终可送达的不同住户人数。

样例1

输入

3
6
5 5
3 3
2 1
1 0
4 4
-2 5
5
2 2
2 2
2 2
1 1
0 1
5
2 1
1 2
0 0
-3 0
0 -3

输出

5
5
3