Kingdom Rush

Ryan은 Ironhide Game Studio가 개발한 싱글 플레이어 타워 디펜스 게임인 Kingdom Rush를 플레이하고 있다. Kingdom Rush에서 플레이어는 아래에 설명된 방식으로 레벨을 완료하여 별을 얻는다. 별이 많을수록 플레이어는 더 강해진다. 따라서 Ryan이 레벨 2을 당장은 완료하지 못할 수도 있지만, 레벨 1에서 별을 얻은 뒤에는 완료할 수 있을지도 모른다.

실제 게임 Kingdom Rush는 이 문제와 완전히 같은 방식으로 작동하지 않는다. 이 문제를 풀기 위해 게임을 해 본 적이 있을 필요는 없다.

이 문제의 Kingdom Rush에서는 플레이어가 레벨을 완료하면 별 1개 평가 또는 별 2개 평가를 받는다. 이 평가는 플레이어가 다음과 같이 별을 얻을 수 있게 할 수도 있다.

• 플레이어가 이전에 그 레벨을 완료한 적이 없고 별 1개 평가로 완료하면, 그 플레이어는 별 1개를 얻는다.

• 플레이어가 이전에 그 레벨을 완료한 적이 없고 별 2개 평가로 완료하면, 그 플레이어는 별 2개를 얻는다.

• 플레이어가 이전에 그 레벨을 별 1개 평가로만 완료한 적이 있고 이번에 별 2개 평가로 완료하면, 그 플레이어는 별 1개를 더 얻는다.

그 밖의 경우에는 플레이어가 별을 얻을 방법이 없다.

Ryan은 모든 레벨을 당장 완료하지 못할 수도 있다. 각 레벨을 별 1개 평가로 완료하려면 그전에 일정한 수의 별을 얻어야 하며, 그 레벨을 별 2개 평가로 완료하려면 그보다 많거나 같은 수의 별이 필요하다.

예를 들어 레벨이 둘 있다고 가정하자.

• 레벨 1을 별 1개 평가로 완료하려면 별 0개가 필요하고, 별 2개 평가로 완료하려면 별 1개가 필요하다.

• 레벨 2을 별 1개 평가로 완료하려면 별 0개가 필요하고, 별 2개 평가로 완료하려면 별 2개가 필요하다.

Ryan에게 가능한 사건의 진행 순서는 다음과 같다.

• Ryan은 별 0개를 가지고 시작한다. 그는 레벨 1 또는 레벨 2 중 하나를 별 1개 평가로 완료할 수 있다. 그는 레벨 1을 별 1개 평가로 완료하기로 한다. 이제 별이 1개 있다.

• 이제 Ryan은 레벨 2을 별 1개 평가로 완료하거나 레벨 1을 별 2개 평가로 완료할 수 있다. 그는 레벨 1을 별 2개 평가로 완료하기로 한다. 이제 별이 2개 있다.

• 이제 Ryan은 레벨 2을 별 2개 평가로 완료할 수 있다. 그렇게 하면 이제 별이 4개 있다.

• 이제 모든 레벨을 별 2개 평가로 완료하고 별 4개(레벨당 2개)를 얻었으므로 끝났다. 그는 레벨을 3번 완료했다. 레벨 1은 두 번, 레벨 2은 한 번 완료했다.

Ryan은 타워 디펜스 게임을 매우 잘하지만, Kingdom Rush를 최대한 빨리 끝내려면 도움이 필요하다. 모든 레벨에서 별 2개 평가를 얻기 위해 레벨을 몇 번 완료해야 하는지 알아내는 것이 여러분의 임무이다.

제한

메모리 제한: 1GB. 시간 제한: 테스트 세트당 30초. 1 ≤ T ≤ 100. 0 ≤ $a_{i}$ ≤ $b_{i}$ ≤ 2001.

테스트 세트 1 (판정 공개)

1 ≤ N ≤ 10.

테스트 세트 2 (판정 비공개)

1 ≤ N ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 게임에 레벨이 몇 개 있는지를 나타내는 정수 N 하나가 포함된 줄로 시작한다. 이어서 N개의 줄이 주어진다. i번째 줄에는 두 정수 $a_{i}$과 $b_{i}$이 주어진다. 이들은 각각 레벨 i에서 별 하나 평가 또는 별 둘 평가를 얻는 데 필요한 별의 수이다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y은 Ryan이 모든 레벨에서 별 2개 평가를 얻기 위해 레벨을 완료해야 하는 최소 횟수이다. Ryan이 모든 레벨에서 별 2개 평가를 얻는 것이 불가능하다면, 대신 y은 문자열 "Too Bad"(" 문자는 제외하되 대소문자는 정확히 그대로)이어야 한다. 이는 Ryan이 Kingdom Rush를 너무 못해서 게임 전체를 끝낼 수 없다는 뜻이다.

Kingdom Rush는 Ironhide Game Studio가 제작했다. Ironhide Game Studio는 Google Code Jam을 보증하지 않으며 이에 관여하지 않는다.