Laser Alarm

The museum in Byteland has plenty of jewels on display, secured by $n$ laser alarms. Each laser alarm can be considered as a segment in the 3D space. In this task, your job is to test the quality of the laser alarm system. You need to find a plane such that it touches the most laser alarms. Note that if the plane touches the endpoint of a segment, it should also be counted.

The first line contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case:

The first line contains a single integer $n$ ($1 \leq n \leq 50$), denoting the number of laser alarms.

Each of the following $n$ lines contains six integers $x_i$, $y_i$, $z_i$, $x'_i$, $y'_i$ and $z'_i$ ($1 \leq x_i,y_i,z_i,x'_i,y'_i,z'_i \leq 100$), describing a segment that connects $(x_i,y_i,z_i)$ and $(x_i',y_i',z_i')$. It is guaranteed that the two endpoints of each segment do not coincide.

For each test case, output a single line containing an integer, denoting the maximum possible number of laser alarms that can be touched.

1
4
1 1 1 1 1 2
1 1 10 1 1 11
1 10 1 1 10 2
10 1 1 10 1 2

3

2022“杭电杯”中国大学生算法设计超级联赛（3）