킹덤 러시

라이언은 아이언하이드 게임 스튜디오가 만든 1인용 타워 디펜스 게임 킹덤 러시를 한다. 이 게임에서는 레벨을 깨면 별을 얻고, 별이 많을수록 플레이어가 강해진다. 그래서 지금은 2번 레벨을 깨지 못해도 1번 레벨에서 별을 모은 뒤에는 깰 수 있다.

이 문제의 규칙은 실제 게임의 규칙과 다르다. 문제를 풀려고 이 게임을 해 볼 필요는 없다.

이 문제에서는 레벨을 깨면 별 하나 등급이나 별 둘 등급을 받는다. 별은 다음과 같이 얻는다.

• 한 번도 깬 적 없는 레벨을 별 하나 등급으로 깨면 별 1개를 얻는다.
• 한 번도 깬 적 없는 레벨을 별 둘 등급으로 깨면 별 2개를 얻는다.
• 전에 별 하나 등급으로만 깬 레벨을 이번에 별 둘 등급으로 깨면 별 1개를 더 얻는다.

이 세 가지가 아닌 경우에는 별을 얻지 못한다.

라이언이 모든 레벨을 바로 깰 수 있는 것은 아니다. 레벨 $i$를 별 하나 등급으로 깨려면 별이 $a_i$개 있어야 하고, 별 둘 등급으로 깨려면 별이 $b_i$개 있어야 한다. $b_i$는 $a_i$보다 작지 않다.

예를 들어 레벨이 두 개인 경우를 보자. 1번 레벨은 별 하나 등급에 별 0개, 별 둘 등급에 별 1개가 필요하고, 2번 레벨은 별 하나 등급에 별 0개, 별 둘 등급에 별 2개가 필요하다. 라이언은 다음처럼 진행할 수 있다.

1. 별 0개로 시작하니 1번 레벨이나 2번 레벨을 별 하나 등급으로 깰 수 있다. 1번 레벨을 별 하나 등급으로 깨고 나면 별이 1개다.
2. 이제 2번 레벨을 별 하나 등급으로, 또는 1번 레벨을 별 둘 등급으로 깰 수 있다. 1번 레벨을 별 둘 등급으로 깨고 나면 별이 2개다.
3. 이제 2번 레벨을 별 둘 등급으로 깰 수 있다. 그렇게 하면 별이 4개다.
4. 모든 레벨이 별 둘 등급이 되었고, 별은 레벨마다 2개씩 모두 4개다. 레벨을 깬 횟수는 3번이고, 1번 레벨을 두 번, 2번 레벨을 한 번 깼다.

모든 레벨에서 별 둘 등급을 받으려면 라이언이 레벨을 최소 몇 번 깨야 하는지 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 게임의 레벨 개수 $N$이 주어진다. 이어지는 $N$개 줄 가운데 $i$번째 줄에는 정수 $a_i$와 $b_i$가 주어진다. $a_i$는 레벨 $i$에서 별 하나 등급을 받는 데 필요한 별의 개수이고, $b_i$는 별 둘 등급을 받는 데 필요한 별의 개수다.

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 모든 레벨에서 별 둘 등급을 받기까지 라이언이 레벨을 깨야 하는 최소 횟수다. 모든 레벨에서 별 둘 등급을 받는 것이 불가능하면 $y$ 자리에 Too Bad를 출력한다. 대소문자는 그대로 지켜야 한다.