我很荣幸能在这里向大家介绍我自己。我的名字是 Aloysius Benjy Cobweb Dartagnan Egbert Felix Gaspar Humbert Ignatius Jayden Kasper Leroy Maximilian。作为一名讲故事的人，今天我决定为大家讲述一个关于英雄 Huriyyah 和怪物们的故事。

很久以前，城里的居民饱受 $n$ 只强大怪物的折磨。它们吃掉独自外出的幼童，甚至杀害无辜的人。在英雄出现之前，这种恐惧已经笼罩了人们几十年。为了这些不幸的市民，Huriyyah 出发前往森林，那里是怪物们的老巢，并与 $n$ 只凶猛残暴的怪物展开了战斗。第 $i$ 只怪物的生命值为 $HP_i$，攻击力为 $ATK_i$。

他们在洞穴中进行了一场回合制战斗。每一秒，英雄 Huriyyah 首先会受到怪物的攻击，受到的伤害是所有存活怪物攻击力的总和。然后，他选择一只怪物进行攻击。该怪物会受到 $k$ 点伤害（其生命值减少 $k$），其中 $k$ 是该怪物此前被攻击的次数。也就是说，对于每只怪物，Huriyyah 第一次攻击它时造成的伤害为 $1$，第二次攻击造成的伤害为 $2$，第三次为 $3$，以此类推。如果某只怪物的生命值小于或等于零，它就会死亡。当所有怪物都被消灭时，英雄获胜。

现在，聪明的观众们，你们能计算出我们的英雄在赢得战斗前所受到的总伤害的最小值吗？

输入格式

输入包含多组测试数据，第一行是一个正整数 $T$，表示测试数据的组数，最多为 $10^3$。

对于每组测试数据，第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示怪物的数量。接下来的 $n$ 行中，第 $i$ 行包含两个整数 $HP_i$ 和 $ATK_i$ ($1 \le HP_i, ATK_i \le 10^5$)，描述了一只怪物。

保证所有测试数据中 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行 Case #x: y，其中 $x$ 是从 $1$ 开始的测试数据编号，$y$ 是英雄所受到的总伤害的最小值。

样例

样例输入 1

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

样例输出 1

Case #1: 19
Case #2: 14