RT。本人在赛时只想着骗分，但是同样过了后两个点。

大致思路是：对小数据 $O(n^2)$ 暴力，大数据先判断能不能两个折点就行（这里 $O(n)$），不行输出 $3$。

后两个点是不是都没有答案为 $4$ 的时候？是数据出水了还是这是个神奇性质？

代码如下：

int sum[1003][1003], sumx[N], sumy[N], t, n;
namespace Sol1 {
	void cln() {
		for (int i = 0; i <= n; i++) sumx[i] = sumy[i] = 0;
		for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) sum[i][j] = 0;
	}
	bool solwith1() {
		for (int i = 1; i <= n; i++) if (sumx[i] == (n >> 1) || sumy[i] == (n >> 1)) return 1;
		return 0;
	}
	bool solwith2() {
		for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
				if (sum[n][j] - sum[i - 1][j] == (n >> 1)) return 1;
		for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
				if (sum[i][n] - sum[i][j - 1] == (n >> 1)) return 1;
		return 0;
	}
	void nowread() {
		cln();
		for (int i = 1; i <= n; i++) {
			int x = read(), y = read();
			sumx[x]++, sumy[y]++, sum[x][y]++;
		}
		for (int i = 1; i <= n; i++) sumx[i] += sumx[i - 1], sumy[i] += sumy[i - 1];
		for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
				sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		if (solwith1()) {
			puts("2");
			return;
		}
		if (solwith2()) {
			puts("3");
			return;
		}
		puts("4");
	}
}
namespace Sol2 {
	void cln() {
		for (int i = 0; i <= n; i++) sumx[i] = sumy[i] = 0;
	}
	bool solwith() {
		for (int i = 1; i <= n; i++) if (sumx[i] == (n >> 1) || sumy[i] == (n >> 1)) return 1;
		return 0;
	}
	void nowread() {
		cln();
		for (int i = 1; i <= n; i++) {
			int x = read(), y = read();
			sumx[x]++, sumy[y]++;
		}
		for (int i = 1; i <= n; i++) sumx[i] += sumx[i - 1], sumy[i] += sumy[i - 1];
		puts(solwith() ? "2" : "3");//并没有处理4
	}
}
signed main() {
//	freopen("ex_line2.in","r",stdin);
//	freopen("ans.out","w",stdout);
	t = read();
	for (int i = 1; i <= t; i++) {
		n = read();
		if (n <= 1000) Sol1::nowread();
		else Sol2::nowread();
	}
	return Strelitzia_H;
}