说明

小w是个魔法师，他有一块残缺的栅栏，是由n块并排在一起的木板构成的，已知每块木板的初始高度为ai（单位cm），他有一种魔法，他可以让第i块木板高度增大1cm但是需要花费对应的bi的能量，现在魔法师小w想要让每块木板与和它相邻的木板的高度都不相同，但是他只是个魔法师，不知道最少花费多少能量才能实现，聪明的你能帮帮他吗？

输入格式

第一行一个整数q(1≤q≤3e5),表示有多少组询问。

每组询问的第一行给出一个整数n（1≤n≤3e5）,表示有n块木板。

接下来n行，每行给出两个整数ai,bi(1<=ai,bi<=1e9)。

保证所有询问的n的和不超过3e5,每组询问的答案不超过1e18。

输出格式

对于每组询问，输出一个整数表示最少花费的能量。

样例

3
3
2 4
2 1
3 5
3
2 3
2 10
2 6
4
1 7
3 3
2 6
1000000000 2

2
9
0

提示

对于第一组询问，已知三块木板高度为2cm,2cm,3cm,可以将第二块木板高度提高2cm，最小花费就是2

对于第二组询问，已知三块木板高度为2cm,2cm,2cm,可以将第一块和第三块高度各增加1cm,最小花费就是3+6=9

对于第三组询问，发现木板初始高度已经满足条件，不需要修改。