机器人

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

有一个机器人,在一个神秘的小屋里走着,上面有一些开关。现在这个机器人需要将这些开关全部打开,但是由于机器人程序问题,每次走到开关位置时,都会去改变一下开关的状态(由开变关,或由关变开),如果这个开关开启之后再关上那么会有意想不到的后果,为了避免这种情况出现,所以机器人只能走到每一个开关上有且只有一次。而且这个机器人高度智能化,从现在所处的位置到下一个开关处最多只会拐一次弯(如果两点的坐标xy其中之一相同,则不会拐弯,否则只拐一次弯)

我们想知道机器人打开所有开关用的最长步数是多少?比如从位置(x,y)到(x,y+1)算一步,聪明的你肯定懂一步的其他几种情况。

Input

第一行输入T,表示有T个case,每个case中: 第一行输入一个数n,表示开关个数(n<=15) 接下来有n行,每行两个整数x,y表示开关坐标0<=x,y<=1000 机器人的起始位置可以任意设置,但是必须在某一开关处。

Output

每个样例输出一个数,表示最长的步数

Sample Input

2
2
1 1
2 2
3
1 1
2 2
3 3

Sample Output

2
6

Hint

Source

from friend

提交代码