你正在玩另一个电脑游戏,现在你必须杀死 $$$n$$$ 怪物。这些怪物站成一圈,顺时针编号从$$$1$$$到$$$n$$$。最初,第 $$$i$$$ 个怪物拥有 $$$a_i$$$ 生命值。
你可以射击怪物来杀死它们。每次射击只需要一颗子弹,并使目标怪物的生命值降低 $$$1$$$(对其造成 $$$1$$$ 伤害)。此外,当某个怪物 $$$i$$$ 的生命值变为 $$$0$$$ 或低于 $$$0$$$ 时,它会死亡并爆炸,对下一个怪物造成 $$$b_i$$$ 伤害(如果 $$$i < n$$$,则为怪物 $$$i + 1$$$,如果 $$$i = n$$$,则为怪物 $$$1$$$)。如果下一个怪物已经死了,那么什么也不会发生。如果爆炸杀死了下一个怪物,它也会爆炸,对后面的怪物造成伤害,并可能引发另一次爆炸,依此类推。
你必须计算杀死圈内所有 $$$n$$$ 怪物所需发射的最少子弹数量。
输入
第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 150000$$$) — 测试用例的数量。
然后是测试用例,每个测试用例都以一行开头,其中包含一个整数 $$$n$$$ ($$$2 \le n \le 300000$$$) — 怪物的数量。接下来是 $$$n$$$ 行,每行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^{12}$$$) — 圆圈中第 $$$i$$$ 怪物的参数。
保证所有测试用例中的怪物总数不超过$$$300000$$$。
输出
对于每个测试用例,打印一个整数 - 杀死所有怪物所需发射的最少子弹数量。
示例
输入 #1
1 3 7 15 2 14 5 3
输出 #1
6