Kingdom Rush (Large)

Ryan is playing Kingdom Rush, a single-player tower defense game developed by Ironhide Game Studio. In this problem's Kingdom Rush, a player earns stars by completing levels under the rules below. More stars make the player stronger, so Ryan might not be able to complete level 2 right away and still be able to complete it after earning stars from level 1.

The real game Kingdom Rush does not work the same way as this problem. You do not need to have played the game to solve it.

In this problem, when a player completes a level, that run is given a 1-star rating or a 2-star rating. The rating earns stars as follows.

• If the player has never completed the level before and completes it with a 1-star rating, the player earns 1 star.
• If the player has never completed the level before and completes it with a 2-star rating, the player earns 2 stars.
• If the player has only completed the level before with a 1-star rating and completes it this time with a 2-star rating, the player earns 1 more star.

In every other case the player earns no stars.

Ryan cannot complete every level right away. For each level, he needs at least a certain number of earned stars before he can complete it with a 1-star rating, and he needs a larger or equal number of stars to complete that level with a 2-star rating.

For example, suppose there are two levels.

• Level 1 requires 0 stars to complete with a 1-star rating, and 1 star to complete with a 2-star rating.
• Level 2 requires 0 stars to complete with a 1-star rating, and 2 stars to complete with a 2-star rating.

Here is one possible series of events for Ryan.

1. Ryan starts with 0 stars. He can complete either level 1 or level 2 with a 1-star rating, and he chooses level 1 with a 1-star rating. Now he has 1 star.
2. Now he can either complete level 2 with a 1-star rating or complete level 1 with a 2-star rating. He completes level 1 with a 2-star rating. Now he has 2 stars.
3. Now he can complete level 2 with a 2-star rating. He does that, and now he has 4 stars.
4. He is done, having completed every level with a 2-star rating and earned 4 stars (2 per level). He completed levels 3 times: level 1 twice and level 2 once.

Ryan is great at tower defense games, but he needs help to beat Kingdom Rush as quickly as possible. Find the minimum number of times he must complete levels in order to earn a 2-star rating on every level.

The first line of the input gives the number of test cases $T$. $T$ test cases follow.

Each test case starts with a line containing a single integer $N$, the number of levels in the game. $N$ lines follow. The $i$th of them contains two integers $a_i$ and $b_i$: the number of stars it takes to earn a one-star rating and the number of stars it takes to earn a two-star rating on level $i$.

Limits

• $1 \le T \le 100$
• $0 \le a_i \le b_i \le 2001$
• $1 \le N \le 1000$

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 minimum number of times Ryan must complete levels in order to have earned a 2-star rating on every level.

If it is impossible for Ryan to earn a 2-star rating on every level, print Too Bad in place of $y$, without the quotes and with exactly that capitalization.