Kiana's Parabolic Assault

Kiana is addicted to a mysterious game played on the plane. A slingshot is fixed at the origin \((0,0)\). In each move, Kiana can fire a red bird into the first quadrant. The bird follows a parabolic trajectory of the form \(y = ax^2 + bx\), where the parameters \(a\) and \(b\) are chosen arbitrarily by Kiana subject to the constraint \(a<0\) (with \(a\) and \(b\) being real numbers). The bird vanishes once it touches the \(x\)-axis again.

In one level of the game, there are \(n\) green pigs located in the first quadrant; the \(i\)th pig is at \((x_i, y_i)\). A pig is eliminated if a bird's trajectory passes through its position. Note that a single bird may eliminate multiple pigs if they all lie exactly on the same parabolic trajectory. For example, if pigs are at \((1,3)\) and \((3,3)\), Kiana can fire a bird with the trajectory \(y = -x^2+4x\), which will eliminate both pigs.

To make the game easier, Kiana also inputs some mysterious commands (detailed in the input format) which allow her more freedom in choosing the shot parameters. With these commands, she can pick any trajectory of the form \(y = ax^2 + bx\) (with \(a<0\)) to eliminate one or more pigs.

Your task is: given \(T\) test cases, each describing a level with \(n\) pigs, determine the minimum number of birds that Kiana needs to fire to eliminate all the pigs.

Problem Transformation

Notice that for any pig at \((x_i,y_i)\) with \(x_i>0\), if we divide the equation \(y=ax^2+bx\) by \(x\) (and denote \(p = y/x\)), we get
    \(p = ax + b\).
Thus, a pig located at \((x_i,y_i)\) can be represented by \((x_i, p_i)\) where \(p_i = y_i/x_i\), and a shot corresponds to choosing a line \(p = ax + b\) with \(a < 0\). A shot will eliminate pig \(i\) if and only if
    \(p_i = a x_i + b\).

In other words, one shot can eliminate a group of pigs if and only if the corresponding points \((x_i, y_i/x_i)\) are collinear on a line with a negative slope. Note that if a pig does not share a line (with \(a<0\)) with any other pig, it must be eliminated individually.

Compute the minimum number of lines of the form \(p = ax+b\) (with \(a<0\)) needed such that every pig is covered by at least one line.

inputFormat

The first line contains an integer \(T\) (\(1 \leq T \leq 20\)) representing the number of test cases.

For each test case, the first line contains an integer \(n\) (\(1 \le n \le 15\)) --- the number of pigs. Each of the following \(n\) lines contains two real numbers \(x_i\) and \(y_i\) (with \(x_i, y_i > 0\)), representing the coordinates of a pig.

Note: The mysterious commands allow Kiana to choose any parabolic trajectory \(y = ax^2+bx\) with \(a<0\) freely. They do not affect the input format.

outputFormat

For each test case, print a single integer --- the minimum number of birds (shots) needed to eliminate all the pigs.

sample

3
2
1 3
3 3
3
1 2
2 1
3 2
4
1 4
2 3
3 2
4 1

1
2
1