This page is still under construction.

Parts of this page are still being built. What you see may change.

Find the Marbles

Interview

Time limit1sMemory limit128 MB

Summary
Given up to 99 distinct integer points per test case, report the largest number of points that lie on one straight line.
Level

Medium5 of 10

Topics
Geometry, Hash map
Solved
No attempts yet

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 TT. Each test case begins with a line holding the number of marbles NN, where 1<N<1001 < N < 100. Each of the next NN 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 xx is the case number starting from 1 and MM is the largest number of marbles lying on a single straight line.

Examples1

  1. Example 1

    Input
    2
    5
    1 1
    2 2
    3 3
    5 10
    6 11
    3
    4 5
    6 7
    8 8
    
    Expected output
    Case #1: 3
    Case #2: 2