Find the Marbles
InterviewTime limit1sMemory limit128 MB
Given up to 99 distinct integer points per test case, report the largest number of points that lie on one straight line.
Problem
A group of friends is playing a game called "Find the Marbles". Someone scatters a handful of marbles on the ground, and each marble sits at an integer coordinate in the plane. A player picks one straight line and walks along it, so that player collects exactly the marbles lying on the chosen line. Whoever collects the most marbles on a single line wins. Report how many marbles the winner collected.
Input
The first line contains the number of test cases . Each test case begins with a line holding the number of marbles , where . Each of the next lines contains two integers separated by a space, the coordinates of one marble. No coordinate pair is given twice.
Output
For each test case, print one line in the format Case #x: M, where is the case number starting from 1 and is the largest number of marbles lying on a single straight line.