New Elements: Part 1

The first two paragraphs (not counting this one) of this problem and "New Elements: Part 2" are identical. The problems can otherwise be solved independently. You do not need to read or solve one to read or solve the other.

Muriel is on the path to discovering two new elements that she has named Codium and Jamarium. She has not been able to isolate them yet, but she wants to start investigating properties like their atomic weights by indirect means. Muriel works with a single isotope of Codium and a single isotope of Jamarium, so their atomic weights are strictly positive integers.

Muriel created $N$ different molecules. Each molecule contains one or more atoms of Codium and one or more atoms of Jamarium, and no other elements. She knows how many atoms of each element each molecule contains. The molecular weight of a molecule is the sum of the atomic weights of all the atoms it contains.

As a first step toward finding exact molecular weights and atomic weights, Muriel wants to sort the molecules by strictly increasing molecular weight. To judge how hard that task is, she wants to know how many orders are valid given only the information she has now. An ordering is valid if there exist atomic weights for Codium and Jamarium such that the ordering is strictly increasing in molecular weight.

For example, represent each molecule by its pair of Codium and Jamarium counts. If Muriel has three molecules (1, 1), (2, 1), and (1, 2), two orderings can be strictly increasing: (1, 1), (1, 2), (2, 1) and (1, 1), (2, 1), (1, 2). The first ordering is valid when Codium is heavier than Jamarium. The second is valid when Jamarium is heavier. When both elements have the same atomic weight, (1, 2) and (2, 1) have the same molecular weight, so no strictly increasing ordering exists in that case.

The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains a single integer N, the number of molecules. Each of the next N lines contains two integers $C_i$ and $J_i$, the number of Codium and Jamarium atoms in the i-th molecule.

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 total number of valid orderings as defined above.

• $1 \le T \le 100$.
• $1 \le C_i \le 10^9$ for all $i$.
• $1 \le J_i \le 10^9$ for all $i$.
• $(C_i, J_i) \ne (C_j, J_j)$ for all $i \ne j$. All molecules are different.

Sample Case #1 is explained in the statement.

In Sample Case #2, the two valid orderings are (1, 2), (2, 1), (2, 4), (4, 2) and (2, 1), (1, 2), (4, 2), (2, 4). The ordering (1, 2), (2, 1), (4, 2), (2, 4) is invalid. If (1, 2) is strictly lighter than (2, 1), then (2, 4), which is exactly twice as heavy as (1, 2), must be strictly lighter than (4, 2), which is exactly twice as heavy as (2, 1).