Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

Chef is working with lines on a 2-D plane.
He knows that every line on a plane can be clearly defined by three coefficients A, B and C: any point (x, y) lies on the line if and only if A * x + B * y + C = 0.
Let's call a set of lines to be perfect if there does not exist a point that belongs to two or more distinct lines of the set.
He has a set of lines on a plane and he wants to find out the size of the largest perfect subset of this set.

------ Input ------

The first line of input contains one integers T denoting the number of test cases.
Each test case consists of one integer N denoting number of lines.
Next N lines contain 3 space-separated integers each denoting coefficients A, B and C respectively.

------ Output ------

For each test case output the cardinality of the largest perfect subset in a single line.

------ Constraints ------

$1 ≤ N ≤ N_{max}$
$Sum over all N for all test cases ≤ NS_{max}$
$|A|, |B|, |C| ≤ 10^{9}$
$For a line with coefficients A, B and C either A or B is not zero.$

------ Subtasks ------

$Subtask #1 [35 points]: N_{max} = 5000, NS_{max} = 50000$
$Subtask #2 [65 points]: N_{max} = NS_{max} = 10^{5}$

----- Sample Input 1 ------
1
5
1 0 0
1 2 3
3 4 5
30 40 0
30 40 50
----- Sample Output 1 ------
2
----- explanation 1 ------
Lines 3x + 4y + 5 = 0 and 30x + 40y + 0 = 0 form a biggest perfect subset.

见题面

见题面