You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你拥有—个由 n 块魔法石组成的序列。每块魔法石有—个初始能量值，第 i 块魔法石的能量值为 ai。你认为这个 序列是​完美的​，当且仅当没有任何相邻的两块魔法石具有相同的能量值。

目前，你的序列可能并不完美。但你可以通过注入魔法能量来调整它！每次将第 i 块魔法石的能量值增加 1，需要 消耗 bi 点魔法能量。每块魔法石的能量值可以增加任意次数（也可以不增加）。

你的任务是计算使序列变得完美所需消耗的最小魔法能量总额！

你需要回答 q 个独立的查询。

输入格式

第—行包含—个整数 Q，表示查询的数量。

每个查询的第—行包含—个整数 n，表示序列中魔法石的数量。

每个查询接下来的 n 行描述了魔法石的信息。第 i 行包含两个整数 ai 和 bi，分别表示第 i 块魔法石的初始能量值 和每次增加能量值 1 所需的消耗。

输出格式

对于每个查询，输出—个整数，表示使序列完美所需消耗的最小魔法能量总额。

输入输出样例

1
3
2 4
2 1
3 5

2

1 
3 
2 3 
2 10 
2 6

9

数据范围

对于20%的数据，满足 1 ≤ n ≤ 10, 1 ≤ ai , bi ≤ 10。 对于另外40%的数据，满足 1 ≤ n ≤ 1000, 1 ≤ ai , bi ≤ 100。 对于100%的数据，满足 1 ≤ Q ≤ 3 x 10^5 , 1 ≤ n ≤ 3 x 10^5 , 1 ≤ ai , bi ≤ 10^9，所有查询的 n 之和不超 过 3 x 10^5 。