Plane Division

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is working with lines on a 2D 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 spaceseparated 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}
Example
Input: 1 5 1 0 0 1 2 3 3 4 5 30 40 0 30 40 50 Output: 2
Explanation
Lines 3*x + 4*y + 5 = 0 and 30*x + 40*y + 0 = 0 form a biggest perfect subset.
Author:  cenadar 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/PLANEDIV 
Tags  cenadar, dec15, euclidean, gcd, parallel, sets, simple, sorting 
Date Added:  19092015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 