Points Cover

The Research Project for Competitions (RPC) rises again with a new mathematical task. This task is related with simple geometrical concepts, specifically with points and lines. A point is a precise location or place on a plane, usually represented by a dot. It is important to understand that a point is not a thing, but a place. For instance we indicate the position of a point by placing a dot with a pencil. This dot may have a diameter of, say, 0.2mm, but a point has no size. No matter how far you zoomed in, it would still have no width. Since a point is a place, not a thing, it has no dimensions. If a set of points all lie in a straight line, they are called “collinear”. If a set of points all lie on the same plane, they are called ’coplanar’. For this problem we will use coplanar points in 2D plane; for instance, points will be located using coordinates X and Y . Then a line is a geometrical object that is straight, infinitely long and infinitely thin. It goes off in both directions forever, and is perfectly straight. A line, strictly speaking, has no ends. It has zero width. For instance, if you draw a line with a pencil, examination with a microscope would show that the pencil mark has a measurable width. The pencil line is just a way to illustrate the idea on paper. In geometry however, a line has no width. If a set of points are lined up in such a way that a line can be drawn through all of them, the points are said to be collinear. For this problem there will be a cloud of points in the 2D plane and you must find the minimum amount of lines that must be drawn in order to cover all the points. Also you must take into account an important restriction: the lines can only be drawn parallel to the coordinate axis. Input A integer number T ≤ 150 representing the number of cases and for each one: first a line with one integer 1 ≤ N ≤ 50000, the number of points. Then follow N lines with the coordinates of the points, not necessarily distinct. For each coordinate, two space-separated integer numbers will be given, the X and Y coordinate value respectively (1 ≤ X, Y ≤ 50000). Output For each case you must print an integer number with an end of line: the minimum amount of lines parallel to coordinate axis that must be drawn in order to cover all the given points. Sample Input 3 1 34 4 11 21 12 22 10 11 12 21 22

2/2 23 24 32 42 33 44 Sample Output 1 2 4