题目描述

城堡镇，顾名思义有一座城堡，但这座城堡并不是一开始就有的。

这座城堡是怎么修建起来的呢？镇上原来总共有 $n$ 栋建筑。把镇看成一个二维平面的话，第 $i$ 栋建筑的坐标就是 $(x_i,y_i)$，并且恰好为一个整点。

镇民们想修建一座城堡在整点 $(X,Y)$。因为要服务镇里的所有人，所以他们希望城堡离所有建筑的距离之和最小。其中，两座建筑 $(x_1,y_1), (x_2,y_2)$ 的距离定义为 $|x_1-x_2| + |y_1-y_2|$。

那么在城堡离所有建筑的距离之和最小的前提下，总共有多少个位置可以修建城堡？注意，所有建筑都必须在整点上，也就是 $(x,y)$ 满足 $x,y$ 均为整数。

然而城堡镇现已为黄沙淹没，现在的人们只能通过古籍来获取当时建筑的数量和位置。然而众说纷坛，所以你需要对 $T$ 个可能的情况做出回答。

输入格式

第一行一个整数 $T$。

接下来 $T$ 组，第一行一个整数 $n$，表示城堡镇原本有 $n$ 座建筑。接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 座建筑的位置。

输出格式

共 $T$ 行，每行一个整数，表示每种情况总共有多少个位置可以修建城堡。

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
4
4
4
3
1

数据范围

• 对于 $30 \%$ 数据，$n, x_i,y_i \leq 100$；
• 对于 $60 \%$ 数据，$x_i,y_i \leq 10^3$；
• 对于 $100 \%$ 数据，$1 \leq T, n$，$\sum n \leq 10^5$，$0 \leq x_i,y_i \leq 10^9$。