Card Shuffle (Large)

Frank likes card games and spends his weekends at game parties in a friend's house. The deck they play with has $M$ cards, each carrying a different number from $1$ to $M$. Frank owns the same automatic shuffling machine his friend uses at those parties, and he knows how it works. The machine shuffles the deck by cutting the pile $C$ times. Cut $i$ takes $B_i$ cards starting at the $A_i$-th card from the top, that is the cards at positions $A_i$ through $A_i + B_i - 1$, and moves them to the top of the pile without changing their order.

One day the usual deck got dirty, so they opened a new one. The new deck went into the shuffling machine exactly as it came, stacked from $1$ at the top down to $M$. Frank wants to use what he knows about the machine to work out which card sits at position $W$ from the top once the shuffle is over.

The first line holds the number of test cases $T$. Each test case then follows in this format.

M C W
A1 B1
...
AC BC

The first line holds three integers $M$, $C$, $W$ separated by a single space, where $M$ is the number of cards, $C$ is the number of cuts, and $W$ is the position Frank asks about. Each of the next $C$ lines holds two integers $A_i$, $B_i$ separated by a single space, meaning that cut $i$ moves the $B_i$ cards starting at the $A_i$-th card from the top to the top of the pile.

Constraints

• $1 \le T \le 200$
• $1 \le C \le 100$
• $1 \le W \le M$
• $1 \le A_i \le M$
• $1 \le B_i \le M$
• $1 \le A_i + B_i - 1 \le M$
• $1 \le M \le 10^9$

For each test case, print one line in this form.

Case #X: P

$X$ is the test case number starting from $1$, and $P$ is the card at position $W$ from the top of the pile after the shuffle.