Mysterious Road Signs

The town of Signfield sits on a perfectly straight, infinitely long road that runs west to east. Along the road is a sequence of $S$ mysterious road signs, each with numbers on both sides. The $i$-th sign (numbered from west to east) is $D_i$ kilometers east of Signfield. It has the number $A_i$ on its west-facing side and the number $B_i$ on its east-facing side.

Nobody in Signfield knows what the signs mean. You suspect that the west-facing numbers are distances to a destination for drivers traveling east, and that the east-facing numbers are distances to a destination for drivers traveling west. Some signs may not fit this theory.

A set of signs is valid if it satisfies both of these rules:

• The set is a contiguous subsequence of all the signs. The entire sequence also counts.
• There exist locations $M$ and $N$, measured in kilometers east of Signfield, where $M$ and $N$ are any numbers (not necessarily positive or distinct), such that every sign in the set satisfies at least one of: $D_i + A_i = M$ or $D_i - B_i = N$.

Find the largest possible number of signs in a valid set, and how many different valid sets of that size exist.

The first line contains $T$, the number of test cases. Each test case begins with a line containing $S$. Then $S$ lines follow, and the $i$-th of them contains $D_i$, $A_i$, and $B_i$. The signs are given in west-to-east order.

For each test case, print one line in the form Case #x: y z. Here $x$ is the test case number starting from 1, $y$ is the largest size of a valid set, and $z$ is the number of valid sets of that size.

• $1 \le T \le 60$.
• $1 \le D_i \le 10^6$ for all $i$.
• $D_i < D_j$ for all $i < j$.
• $1 \le A_i \le 10^6$ for all $i$.
• $1 \le B_i \le 10^6$ for all $i$.

A single sign always forms a valid set, because $M$ and $N$ can be chosen to match it. A set that works for several $M$ and $N$ pairs still counts only once. A number on one side of a sign cannot stand in for the number on the other side.