P13316 [GCJ 2012 #1A] Kingdom Rush

Kingdom Rush 由 Ironhide Game Studio 开发。Ironhide Game Studio 未参与本题，也未对 Google Code Jam 进行任何背书。

Ryan 正在玩 Kingdom Rush，这是一款由 Ironhide Game Studio 开发的单人塔防游戏。在 Kingdom Rush 中，玩家通过完成关卡获得星星，具体规则如下。星星越多，玩家就越强大；因此，Ryan 也许暂时无法完成第 2 关，但他可以先通过第 1 关获得星星后再挑战第 2 关。 真实的 Kingdom Rush 游戏机制与本题略有不同。你不需要玩过这款游戏也能解题。 在本题描述的 Kingdom Rush 里，当玩家完成某一关时，可以获得 1 星或 2 星的评价。获得星星的具体规则如下： * 如果玩家从未通关该关卡，并以 1 星评价通关，则获得 1 颗星。 * 如果玩家从未通关该关卡，并以 2 星评价通关，则获得 2 颗星。 * 如果玩家之前以 1 星评价通关过该关卡，现在以 2 星评价再次通关，则再获得 1 颗星。 除此之外，玩家无法再通过该关卡获得星星。 Ryan 可能并不能立刻完成所有关卡。对于每一关，在以 1 星评价完成前，需要至少获得 $a_i$ 颗星；而以 2 星评价完成前，需要至少获得 $b_i$ 颗星，且 $b_i \geq a_i$。 例如，假设有两关： * 第 1 关：以 1 星评价完成需要 0 颗星，以 2 星评价完成需要 1 颗星。 * 第 2 关：以 1 星评价完成需要 0 颗星，以 2 星评价完成需要 2 颗星。 Ryan 可能的通关流程如下： 1. Ryan 初始有 0 颗星。他可以选择以 1 星评价完成第 1 关或第 2 关。他选择以 1 星评价通关第 1 关，此时有 1 颗星。 2. 现在，Ryan 可以选择以 1 星评价通关第 2 关，或以 2 星评价再次通关第 1 关。他选择以 2 星评价通关第 1 关，此时有 2 颗星。 3. 现在，Ryan 可以以 2 星评价通关第 2 关。他完成后共有 4 颗星。 4. 此时他已完成所有关卡的 2 星评价，累计获得 4 颗星（每关 2 颗）。他一共通关了 3 次：第 1 关两次，第 2 关一次。 Ryan 很擅长塔防游戏，但他需要你的帮助来尽快通关。你的任务是计算，为了让每一关都获得 2 星评价，Ryan 至少需要通关多少次。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据第一行为整数 $N$，表示该游戏包含的关卡数。接下来 $N$ 行，每行两个整数 $a_i$ 和 $b_i$，分别表示第 $i$ 关以 1 星和 2 星评价完成所需的星星数。

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 表示 Ryan 至少需要通关的次数，以使每一关都获得 2 星评价。如果无法让每一关都获得 2 星评价，则输出 "Too Bad"（不带引号，大小写严格一致）。这表示 Ryan 没有能力完成整个游戏。

**限制条件** - $1 \leq T \leq 100$ - $0 \leq a_i \leq b_i \leq 2001$ **测试集 1（15 分，结果可见）** - $1 \leq N \leq 10$ **测试集 2（18 分，结果隐藏）** - $1 \leq N \leq 1000$ 翻译由 ChatGPT-4.1 完成。