Wormhole in One

You are participating in an inter-galactic hyperspace golf competition, and you have advanced to the final round! You are really determined to triumph, so you want to prepare a winning strategy.

In hyperspace golf, as in conventional golf, you hit a ball with a club, which sends the ball in a direction you choose. The playing field is a 2-dimensional plane with points representing the holes. The ball is also a point, and you choose where it starts, as long as it is not at the same place as a hole.

Players may turn some pairs of holes into wormholes by linking them together. Each hole can stay a normal hole or be linked to at most one other hole (never to itself). Wormholes are undirected, so the ball can traverse them in either direction.

The environment is frictionless. When you hit the ball, it moves in a straight line and keeps that direction forever unless it reaches a hole, which we call h. When the ball touches h, it stops if h is not linked to another hole. If h is linked to another hole h', the ball immediately comes out of h' and keeps moving in the same direction.

You know the location of each hole. You want to maximize the number of distinct holes you can touch with a single hit. To do so, you pick the ball's starting location, the direction to send the ball, and which pairs of holes, if any, to link as wormholes. The ball cannot start at the same place as a wormhole. When the ball goes through a wormhole, both the hole it enters and the hole it exits count toward your total. Each hole counts once, even if the ball enters or exits it several times. If the ball stops in a hole, that hole also counts.

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with one line containing a single integer N: the total number of holes. The following N lines each contain two integers, Xi and Yi, the X and Y coordinates of the i-th hole.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of distinct holes you can touch if you make optimal decisions as described above.

1 <= T <= 100.

$-10^9 \le X_i \le 10^9$ for all i.

$-10^9 \le Y_i \le 10^9$ for all i.

$(X_i, Y_i) \ne (X_j, Y_j)$ for all $i \ne j$. No two holes are at the same coordinates.

In Sample Case #1, we can connect the two holes with a wormhole, so we can touch both of them by sending the ball into either one. Without the wormhole, the ball would stay in the first hole it touches, so it could not touch more than one hole.

In Sample Case #2, we can connect the holes at (0, 0) and (5, 5). We can then hit the ball from (4.9, 5) in the positive horizontal direction. It first touches the hole at (5, 5), goes into it, and comes out of the hole at (0, 0) with the same horizontal direction. Finally it touches the hole at (5, 0) and stops, since that hole has no wormhole.

In Sample Case #3, we connect the holes at (0, 0) and (5, 0), and also the holes at (3, 2) and (5, 5). Hitting the ball from (4, -1) toward the hole at (5, 0) makes it touch the holes at (5, 0), (0, 0), (5, 5), and (3, 2), in that order.

In Sample Case #4, we connect the holes at (0, 0) and (1, 1), the holes at (2, 1) and (11, 2), and the holes at (8, 2) and (14, 2). Hitting the ball from (-1, 0) toward the hole at (0, 0) makes it touch the holes at (0, 0), (1, 1), (2, 1), (11, 2), (14, 2), (8, 2), (11, 2), (2, 1), and (3, 1), in that order. The holes at (11, 2) and (2, 1) are touched twice, but each is counted once, since the problem asks for distinct holes.

In Sample Case #5, there is only one hole. We can hit the ball into it without considering wormholes. We can choose any starting location, even outside the coordinate range of the holes.