最近，由 poncle 开发的 Roguelike 卡牌构筑游戏《Vampire Crawlers》已正式发布。在游戏中，玩家在战斗中构筑卡组并出牌以造成伤害。其核心机制是连击系统：当你按法力消耗升序出牌时，伤害倍数会不断叠加。

你当前有 $n$ 张卡牌，其中第 $i$ 张卡牌具有消耗和基础伤害。你需要选择一个顺序来逐一打出所有 $n$ 张卡牌。当你打出一张卡牌时：

• 如果这不是打出的第一张卡牌，且其消耗等于前一张卡牌的消耗加 1，则伤害倍数增加 1。
• 否则，伤害倍数重置为 1。

在更新伤害倍数后，该卡牌造成的伤害计算为其基础伤害乘以倍数。

你需要求出可能的最大总伤害。

输入格式

输入包含多个测试用例。输入的第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示卡牌的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($0 \le a_i \le 10^9$, $1 \le b_i \le 10^6$)，分别表示第 $i$ 张卡牌的消耗和伤害。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一行包含一个整数，表示最大可能的总伤害。

样例

输入格式 1

2
9
1 3
3 10
6 4
1 2
5 8
0 5
2 7
6 1
2 7
1
1000000000 1000000

输出格式 1

105
1000000

说明

对于第一个样例测试用例，按照 $6, 1, 9, 2, 8, 4, 7, 5, 3$ 的顺序打出卡牌。总伤害为 $5 \times 1 + 3 \times 2 + 7 \times 3 + 10 \times 4 + 1 \times 1 + 2 \times 1 + 7 \times 2 + 8 \times 1 + 4 \times 2 = 105$。