Kingdom Rush (큰 입력)

라이언은 Ironhide Game Studio가 만든 싱글 플레이어 타워 디펜스 게임 Kingdom Rush를 하고 있다. 이 문제의 Kingdom Rush에서 플레이어는 아래 규칙대로 레벨을 깨면서 별을 모은다. 별이 많을수록 플레이어가 강해지므로, 지금은 레벨 2를 깰 수 없어도 레벨 1에서 별을 모은 뒤에는 깰 수 있다.

실제 게임 Kingdom Rush의 규칙은 이 문제와 다르다. 문제를 푸는 데 게임 경험은 필요하지 않다.

이 문제에서 플레이어가 레벨을 한 번 깨면 그 판의 평가는 별 1개 또는 별 2개다. 평가에 따라 별을 다음과 같이 얻는다.

• 아직 한 번도 깨지 않은 레벨을 별 1개 평가로 깨면 별 1개를 얻는다.
• 아직 한 번도 깨지 않은 레벨을 별 2개 평가로 깨면 별 2개를 얻는다.
• 전에 별 1개 평가로만 깬 레벨을 이번에 별 2개 평가로 깨면 별 1개를 더 얻는다.

이 밖의 경우에는 별을 얻지 못한다.

라이언이 처음부터 모든 레벨을 깰 수 있는 것은 아니다. 각 레벨마다 별 1개 평가로 깨려면 모아 둔 별이 정해진 개수 이상이어야 하고, 별 2개 평가로 깨려면 그보다 크거나 같은 개수의 별이 필요하다.

예를 들어 레벨이 두 개라고 하자.

• 레벨 1은 별 1개 평가로 깨려면 별 0개, 별 2개 평가로 깨려면 별 1개가 필요하다.
• 레벨 2는 별 1개 평가로 깨려면 별 0개, 별 2개 평가로 깨려면 별 2개가 필요하다.

이때 라이언에게 일어날 수 있는 진행 하나는 이렇다.

1. 별 0개로 시작한다. 레벨 1과 레벨 2 중 어느 쪽이든 별 1개 평가로 깰 수 있고, 여기서는 레벨 1을 별 1개 평가로 깬다. 이제 별이 1개다.
2. 이제 레벨 2를 별 1개 평가로 깨거나 레벨 1을 별 2개 평가로 깰 수 있다. 레벨 1을 별 2개 평가로 깬다. 이제 별이 2개다.
3. 이제 레벨 2를 별 2개 평가로 깰 수 있다. 그렇게 깨면 별이 4개가 된다.
4. 모든 레벨을 별 2개 평가로 깼고 별 4개(레벨당 2개)를 모았다. 레벨을 깬 횟수는 모두 3번으로, 레벨 1이 두 번, 레벨 2가 한 번이다.

라이언은 타워 디펜스를 잘하지만 Kingdom Rush를 가장 빠르게 끝내려면 도움이 필요하다. 모든 레벨에서 별 2개 평가를 받으려면 레벨을 최소 몇 번 깨야 하는지 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 게임의 레벨 수 $N$이 주어진다. 이어지는 $N$개 줄 중 $i$번째 줄에는 두 정수 $a_i$와 $b_i$가 주어진다. 각각 레벨 $i$에서 별 1개 평가를 받는 데 필요한 별의 개수와 별 2개 평가를 받는 데 필요한 별의 개수다.

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 모든 레벨에서 별 2개 평가를 받기 위해 라이언이 레벨을 깨야 하는 최소 횟수다.

모든 레벨에서 별 2개 평가를 받는 것이 불가능하면 $y$ 자리에 Too Bad를 출력한다. 따옴표는 쓰지 않고 대소문자도 이 그대로 써야 한다.