You and your friends live in nn houses. Each house is located on a 2D plane, in a point with integer coordinates. There might be different houses located in the same point. The mayor of the city is asking you for places for the building of the Eastern exhibition. You have to find the number of places (points with integer coordinates), so that the summary distance from all the houses to the exhibition is minimal. The exhibition can be built in the same point as some house. The distance between two points (x1,y1)(x_1,y_1) and (x2,y2)(x_2,y_2) is ∣x1−x2∣+∣y1−y2∣|x_1−x_2|+|y_1−y_2|, where ∣x∣|x| is the absolute value of xx.

Input

First line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains a single integer nn (1≤n≤1000)(1≤n≤1000). Next nn lines describe the positions of the houses (xi,yi)(x_i,y_i) (0≤xi,yi≤109)0≤x_i,y_i≤10^9).

It’s guaranteed that the sum of all nn does not exceed 10001000.

Output

For each test case output a single integer - the number of different positions for the exhibition. The exhibition can be built in the same point as some house.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

output

1
2
3
4
5
6
1
4
4
4
3
1

Note

Here are the images for the example test cases. Blue dots stand for the houses, green — possible positions for the exhibition.


First test case.


Second test case.


Third test case.


Fourth test case.


Fifth test case.


Sixth test case. Here both houses are located at (0,0)(0,0).

Idea

假设最后选定的坐标为 (X,Y)(X,Y)。设坐标 xi≤Xx_i\le X 的个数有 uu，而 xi>Xx_i>X 的坐标有 vv，则 XX 产生的路程贡献为 (uX−∑xi≤Xxi)+(∑xi>Xxi−vX)(uX-\sum\limits_{x_i\le X}x_i)+(\sum\limits_{x_i>X}x_i-vX)；对于 YY 的路程贡献，同理。从式中可以看出，XX 和 YY 相互独立，互不产生影响。接下来只讨论 XX 的取值。

考虑枚举 uu，我们先将 xx 序列升序排列；枚举到 xix_i 时，对于 xi∼xi+1x_i\sim x_{i+1} 种的任何 XX 值，都有 u=iu=i 且 v=n−iv=n-i；令 sumi=∑j=1ixjsum_i=\sum\limits_{j=1}^i x_j，则 XX 产生的贡献为 (2i−n)X+sumn−2sumi(2i-n)X+sum_n-2sum_i，其中 xi≤X<xi+1x_i\le X<x_{i+1}。显然，对于 2i−n<02i-n<0，X=xiX=x_i 为最优；对于 2i−n>02i-n>0，X=xi+1−1X=x_{i+1}-1 为最优；对于 2n−i=02n-i=0，XX 可取 [xi,xi+1−1][x_i,x_{i+1}-1] 中的任意正整数。

用unordered_map<long long,long long>记录贡献为 CC 的 XX 的个数。

值得注意一些细节：若某一 XX 值已经被取过，不可重复计数，需要用unordered_set记录；考虑 X=xnX=x_n 和 X=x1X=x_1 的边界情况；一定要注意枚举到 xix_i 时 XX 的取值范围。

YY 的计算与之同理。

假设 XX 产生的最小的路程贡献为 CXminC_{Xmin}，同理可定义 CYminC_{Ymin}；取到 CXminC_{Xmin} 的 XX 个数为 cxc_x，同理有 cyc_y；答案为 cx×cyc_x\times c_y。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF14586B
Date: 2021 Mar. 3rd
Description: Construction
*******************************************************************/
#include<unordered_map>
#include<iostream>
#include<algorithm>
#include<unordered_set>
using namespace std;
typedef long long ll;
const int N=1003;
int _;
int n;
ll x[N],y[N];
//记录取到贡献C的坐标数
unordered_map<ll,ll>costNumX,costNumY;
//前缀和
ll sumX[N],sumY[N];
//记录取到某一值
unordered_set<int>visX,visY;
ll leastCostX,leastCostY;
int nx,ny;
int main(){
	for(cin>>_;_;_--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>x[i]>>y[i];
		}
		//排序
		sort(x+1,x+1+n);
		sort(y+1,y+1+n);
		for(int i=1;i<=n;i++){
			//预处理前缀和
			sumX[i]=sumX[i-1]+x[i];
			sumY[i]=sumY[i-1]+y[i];
		}
		//清空
		costNumX.clear();
		visX.clear();
		costNumY.clear();
		visY.clear();
		for(int i=1;i<=n;i++){
			if(i>n-i){
				const ll X=x[i];
				const ll Y=y[i];
				const ll costX=(2*i-n)*X-2*sumX[i]+sumX[n];
				const ll costY=(2*i-n)*Y-2*sumY[i]+sumY[n];
				//检验X是否取到
				if(visX.find(X)==visX.end()){
					costNumX[costX]++;
					visX.insert(X);
				}
				if(visY.find(Y)==visY.end()){
					visY.insert(Y);
					costNumY[costY]++;
				}
			}else if(i<n-i){
				if(i<n){
					const ll X=max(x[i+1]-1,x[i]);
					const ll Y=max(y[i+1]-1,y[i]);
					const ll costX=(2*i-n)*X-2*sumX[i]+sumX[n];
					const ll costY=(2*i-n)*Y-2*sumY[i]+sumY[n];
					if(visX.find(X)==visX.end()){
						costNumX[costX]++;
						visX.insert(X);
					}
					if(visY.find(Y)==visY.end()){
						visY.insert(Y);
						costNumY[costY]++;
					}
				}else{
					const ll X=x[n];
					const ll Y=y[n];
					const ll costX=n*X-sumX[n];
					const ll costY=n*Y-sumY[n];
					if(visX.find(X)==visX.end()){
						costNumX[costX]++;
						visX.insert(X);
					}
					if(visY.find(Y)==visY.end()){
						visY.insert(Y);
						costNumY[costY]++;
					}
				}
			}else{
				const ll X=x[i];
				const ll Y=y[i];
				const ll costX=(2*i-n)*X-2*sumX[i]+sumX[n];
				const ll costY=(2*i-n)*Y-2*sumY[i]+sumY[n];
				if(i<n){
					//x[i]没有取过
					//那么x[i]~x[i+1]-1也没有取过
					if(visX.find(X)==visX.end()){
						costNumX[costX]+=max(x[i+1]-x[i],1ll);
						visX.insert(X);
					}else{
						costNumX[costX]+=max(x[i+1]-x[i]-1,0ll);
					}
					if(visY.find(Y)==visY.end()){
						visY.insert(Y);
						costNumY[costY]+=max(y[i+1]-y[i],1ll);
					}else{
						costNumY[costY]+=max(y[i+1]-y[i]-1,0ll);
					}
				}
			}
		}
		leastCostX=leastCostY=0x7f7f7f7f7f7f7f7f;
		for(auto& cX:costNumX){
			leastCostX=min(leastCostX,cX.first);
		}
		for(auto& cY:costNumY){
			leastCostY=min(leastCostY,cY.first);
		}
		//一定要开ll
		cout<<costNumX[leastCostX]*costNumY[leastCostY]<<endl;
	}
	return 0;
}