19193번 - Lines 스페셜 저지다국어

문제

You are given $n$ lines on a plane. Your task is to select the maximum possible number of lines so that among the selected ones, no two lines are the same, no two lines are parallel and no two lines have an intersection at a point with $x = 0$.

입력

The first line of input contains one positive integer $T,ドル the number of test cases. The test cases follow.

Each test case starts with a line containing an integer $n,ドル the number of lines (1ドル \le n \le 3000$). Each of the next $n$ lines of input contain three integers $A,ドル $B$ and $C$ describing a line as a set of points $(x, y)$ for which the equation $A x + B y + C = 0$ holds ($-10^9 \le A, B, C \le 10^9,ドル $A^2 + B^2 > 0$).

The sum of $n$ in the input does not exceed 3000ドル$.

출력

For each test case, first, on a separate line, print the number $k$: the maximum possible number of lines that can be selected. On the next line, print $k$ integers: the numbers of the chosen lines in any order. The lines are numbered starting from 1ドル$ in the order they are given in the input.

If there are several optimal answers, print any one of them.

제한

힌트