Juice Blend

You are throwing a party, and you mix three juices into one drink: apple, banana and carrot. Call them juice A, juice B and juice C.

You decide what share of the drink each juice takes. A share is an integer in parts per ten thousand, and the three shares add up to exactly $10000$.

Each guest has a minimum share for every juice. A guest likes the drink only if the share of each of the three juices is at least that guest's minimum for that juice.

Choose the shares so that as many guests as possible like the drink, and report that number.

The first line contains an integer T, the number of test cases.

Each test case is given as follows.

• One line with the integer N, the number of guests at the party.
• N lines, one per guest, each with three space-separated integers "A B C", the minimum share that guest wants of each juice, in parts per ten thousand. They satisfy $0 \le A, B, C \le 10000$ and $A + B + C \le 10000$.

Limits

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

Print one line per test case, in the order the test cases appear in the input, containing "Case #X: Y". X is the test case number starting from $1$, and Y is the largest number of guests who like the drink.

In the first test case of the first example, each of the three guests wants the drink made from a single juice, and the three juices differ, so only one guest can be satisfied.

In the second test case, any two of the three guests can be satisfied together.

In the third test case, shares of $3334$, $3333$ and $3333$ satisfy all five guests.