题目描述

在平面直角坐标系中，所有坐标均为整数的点称为格点。每个格点的颜色为黑色或白色。 一条从格点 $s$ 到格点 $t$ 的路径是一个由 $m+1$ 个格点组成的序列 $p_1,p_2,\dots,p_{m+1}$，其中 $m$ 为非负整数，$p_1=s,p_{m+1}=t$，且对于任意 $1\leq i\leq m$，格点 $p_i$ 与 $p_{i+1}$ 八邻接。这条路径的距离为 $\displaystyle\sum_{i=1}^{m}\operatorname{dist}(p_i,p_{i+1})$。 两个格点之间的最短路径，是指所有连接这两个格点的路径中距离最短的路径。两个格点之间可能存在多条最短路径。 如果一条路径经过的所有格点（包括两个端点）均为黑色，则称这条路径是黑色的。 如果任意两个黑色格点之间的每一条最短路径都是黑色的，则称当前染色方案为凸包。 初始时，所有格点均为白色，共进行 $q$ 次染黑操作，每次将一个格点变为黑色。请你求出，在这 $q$ 次操作全部完成后，至少还需要将多少个白色格点染成黑色，才能使当前染色方案成为凸包。 【名词解释】 八邻接：对于两个不同格点 $A=(a,b)$ 和 $B=(c,d)$，当且仅当 $|a-c|\in\{0,1\}$ 且 $|b-d|\in\{0,1\}$ 时，称这两个格点八邻接。两个格点之间的距离 $\operatorname{dist}(A,B)$ 定义为 $\sqrt{(a-c)^2+(b-d)^2}$。官方中文

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 10^3\right)$，表示测试数据的组数。每组测试数据描述如下：官方中文

第一行输入一个整数 $q\left(1\leq q\leq 10^5\right)$，表示染色操作次数。 此后 $q$ 行，第 $i$ 行输入两个整数 $x_i,y_i\left(1\leq x_i,y_i\leq 10^4\right)$，表示第 $i$ 次操作染黑的格点坐标。所给点的坐标可能相同。官方中文

保证单个测试文件中所有测试数据的 $q$ 之和不超过 $2\times 10^5$。官方中文

输出格式

对于每组测试数据，新起一行。 输出一个整数，表示至少还需要染黑的白色格点数量。官方中文

说明

在大部分情况下，PyPy 的运行速度优于 Python。本题我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。官方中文