小兔子走进一家商场，偶然发现了一个抽奖活动。这里有 $n$ 个盒子。在第 $i$ 个盒子里，有 $x_i$ 个标有 $2^{a_i}$ 的球。小兔子可以从每个盒子里取出任意数量（包括零个）的球。他所得到的总分是他所选球上数字之和。小兔子能否在抽奖中获奖取决于这个分数。

然而，小兔子并不关心他是否能获奖。他很好奇他可能得到多少种不同的分数。你能帮帮他吗？由于答案可能非常大，请告诉他答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示盒子的数量。所有测试用例的 $n$ 之和不超过 $10^5$。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ ($0 \le a_i \le 10^9$) 和 $x_i$ ($1 \le x_i \le 10^9$)，表示第 $i$ 个盒子里有 $x_i$ 个标有 $2^{a_i}$ 的球。保证 $a_1, a_2, \dots, a_n$ 两两不同。

输出格式

对于第 $x$ 个测试用例，如果答案对 $10^9 + 7$ 取模的结果为 $y$，请在一行中输出 Case #x: y。

样例

输入 1

2
3
1 1
2 1
3 1
3
1 1
2 2
3 3

输出 1

Case #1: 8
Case #2: 18