### 问题描述 maimai 是一个具有八个按键的音游街机游戏，每个按键有固定的坐标 $(x,y)$ 。在游戏中，会有一些音符从屏幕中心飞到按键上，当音符与按键重合的时候，玩家需要按下按键来捕捉音符，从而获取得分。 而你是一名出色的音游玩家，当音符飞过来的时候，你要按照音符的给出顺序依次按下相对应的按钮。你已经知道了一首歌的音符顺序，所以你列了一个长度为 $N$ 的按钮坐标清单。 你有两只手，我们定义你的某一只手第一次触碰到某个按键的代价为 $0$ ，否则其代价为这一次的按键坐标与上一次按键坐标的曼哈顿距离。同时，在你按下某个按键后，为了减轻体力消耗，你的手在执行这一次动作之前只会停留于上一次按下的按键位置。即按完 $A$ 按键之后，手只会放在那个按键上，直到执行"按 $B$ 按键"的指令才会将手从 $A$ 按键移动到 $B$ 按键上。需要注意的是，你有两只手，而不一定是一只手一直在动。 你的体力并不是很多，所以你希望尽可能地减少你的体力代价，因此你需要计算出按照顺序按完所有按钮的最小体力代价是多少。 让我们回忆一下曼哈顿距离的定义，如果第一个按键的坐标为 $(x_1,y_1)$ ，第二个按键的坐标为 $(x_2,y_2)$ ，那么两个按键的曼哈顿距离为 $|x_1-x_2|+|y_1-y_2|$ 。 ### 输入格式 输出存在多组样例，第一行包含一个正整数 $T$ ，表示样例数量。 对于每一个样例，第一行包含一个正整数 $N$ ，表示坐标清单的长度。 接下来 $N$ 行，每行包含该按钮的坐标 $(x_i,y_i)$ ，保证这 $N$ 个坐标最多只有八种不同的坐标且坐标为非负整数。 ### 输出格式 输出仅一行，包含一个整数，表示最小代价。 ### 样例输入 ```text 3 2 0 1 0 2 3 0 1 1 0 1 1 3 4 0 0 1 2 1 ``` ### 样例输出 ```text 0 1 2 ``` ### 说明 对于第一个样例，因为你有两只手，我们可以让左手按第一个按键，右手按第二个按键，因为都是首次所以代价为 $0$ 。对于第三个样例，首先你用左手按下 $(4,0)$ 的按键，其次你用右手按下 $(0,1)$ 的按键，最后将右手从 $(0,1)$ 移动至 $(2,1)$ 上，总共成本为 $0+0+2=2$ ，即最小代价为 $2$ 。 ### 评测数据规模 对于 $20$% 的评测数据， $T=1$ ， $N=10$ 。 对于 $50$% 的评测数据， $1\leq T \leq10$ ， $N \leq 10^3$ 。 对于 $100$% 的评测数据，$1\leq T \leq10$ ， $0 \leq x,y \leq 10^4$ ， $\sum n \leq 2 \times 10^5$ 。