Juice (Small Input)

You are holding a party. The drink you serve is a mix of three juices, apple, banana, and carrot. Call them $A$, $B$, and $C$.

You have to fix the fraction of the drink taken by each juice, $a$, $b$, and $c$. All three are real numbers at least $0$ and satisfy $a + b + c = 1$. Your goal is to maximize the number of guests who like the drink.

Each guest has a minimum fraction they want for every one of the three juices. A guest likes the drink only when all three fractions in the drink are at least that guest's own minimum for that juice. If even one falls short, the guest does not like it.

Determine the largest number of guests you can satisfy with a single best choice of the drink.

The first line contains the number of test cases $T$.

Each test case follows in this form.

• The first line contains the number of guests $N$.
• Each of the next $N$ lines contains one guest's minimum fractions $A$, $B$, and $C$, separated by spaces. The three values are given in parts per ten thousand, that is, as integers on a scale where the whole drink is $10000$, and each lies between $0$ and $10000$. Also $A + B + C \le 10000$.

Limits

• $1 \le T \le 12$
• $1 \le N \le 10$

For each test case, print one line in the form Case #X: Y, where $X$ is the test case number starting from $1$ and $Y$ is the largest number of guests who like the drink. Print the lines in the order the test cases are given.

In the first test case of the example, each of the three guests wants the whole drink to be one single juice, so only one of them can be satisfied.

In the second test case you can pick any two of the three guests and satisfy both.

In the third test case, mixing exactly $1/3$ of each juice makes all five guests like the drink.