Gerrymandering

Gerrymandering is the technique of dividing electoral districts so as to favor one party over another. Originally, voting districts were meant to be reviewed once a decade so as to keep representation roughly equal among voters. Nowadays, the party in power often treats redistricting as a handy tool for securing more seats in future elections. This tends to contradict the original intent, since many voters are effectively disenfranchised — but one does what one can to win an election.

To gerrymander well, you need a program that computes the best districts; it does not matter that the result rarely looks “natural.” In this problem, a number of voting precincts must be divided into exactly two districts. Your program must determine whether a given party can guarantee winning both districts, exactly one district, or no district. Each district must contain at least one precinct, but the two districts need not contain the same (or even a similar) number of precincts.

Party P wins a district when its total number of votes in that district is strictly greater than party Q's total in the same district. If the two totals are equal, P does not win that district.

The first line contains the number $K$ ($K \ge 1$) of data sets in the input. It is followed by $K$ data sets of the following form.

The first line of each data set contains one number $n$ ($1 \le n \le 100$), the number of precincts. It is followed by $n$ lines, each describing one precinct $i$ by two numbers $p_i$ and $q_i$, the number of voters expected to vote for parties P and Q. These numbers are between $0$ and $1000$, inclusive.

For each data set, first output Data Set x: on a line by itself, where $x$ is its number (starting from 1). Then output the maximum number of districts ($0$, $1$, or $2$) that party P can win with optimal gerrymandering.