Statement
你正在参加一场星际超空间高尔夫比赛,并且已经晋级到决赛轮!你非常渴望获胜,所以你想准备一个必胜策略。
在超空间高尔夫中,就像传统高尔夫一样,你用球杆击球,球会朝你选择的方向运动。超空间高尔夫的比赛场地是一个二维平面,平面上的点代表不同的洞。球也用一个点表示,你可以选择球的起始位置,只要它不与洞在同一位置。
由于这是超空间高尔夫,玩家可以将一些洞对连接成虫洞。每个洞既可以保持为普通洞,也可以与至多一个其他洞相连(绝不能与自身相连)。虫洞是无向连接,可以双向穿越。
因为环境无摩擦,当你击球时,球会沿直线方向运动,除非碰到洞,否则会永远保持该方向;称那个洞为 h。碰到洞 h 时,如果 h 没有与另一个洞相连,球就停住。如果 h 与另一个洞 h' 相连,那么球会立即从 h' 出来,并继续沿之前相同的方向运动。
你知道每个洞的位置。你想最大化一次击球能碰到的不同洞的数量。基于这一目标,你可以选择球的起始位置、击球方向,以及将哪些洞对(如果有的话)连接为虫洞。球不能从与虫洞相同的位置开始。当球穿过虫洞时,它进入的洞和出来的洞都计入总数。每个洞只计数一次,即使球多次进入或出来(或两者都有)。如果球停在某个洞里,那个洞也计入总数。
Input
输入的第一行给出测试用例的数量 T。
接下来是 T 个测试用例。每个测试用例开始于一行,包含一个整数 N:洞的总数。接下来的 N 行每行包含两个整数:X$_{i}$ 和 Y$_{i}$,分别表示第 i 个洞的 X 和 Y 坐标。
### 数据范围
- 1 ≤ T ≤ 100.
- -10 ≤ X$_{i}$ ≤ 10, 对于所有
- i.
- -10 ≤ Y$_{i}$ ≤ 10, 对于所有
- (X$_{i}$, Y$_{i}$) ≠ (X$_{j}$, Y$_{j}$),
- 对于所有 i ≠ j. (没有两个洞位于相同坐标。)
- 1 ≤ N ≤ 7.
- 1 ≤ N ≤ 100.
Output
按测试用例顺序逐个输出答案。对于每个测试用例,输出一行,包含 y,其中 y 是如果你按照上述描述做出最优决策时,可以碰到的最大不同洞数。
Examples
Input
5
2
0 0
5 5
3
0 0
5 5
5 0
5
0 0
5 5
5 0
3 2
2 4
7
0 0
1 1
2 1
3 1
8 2
11 2
14 2
1
-1000000000 1000000000Output
2
3
4
7
1Constraints
- Time limit: 10000 ms
- Memory limit: 1048576 KB
- Tag: geometry
- Tag: graph
- Tag: search