D. Сделаем забор великим снова
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть забор, состоящий из $$$n$$$ вертикальных досок. Ширина каждой доски равна $$$1$$$. Высота $$$i$$$-й доски равна $$$a_i$$$. Вы считаете забор великим, если все соседние доски имеют разную высоту. Формально, забор великий, если для любого индекса от $$$2$$$ до $$$n$$$, выполняется условие $$$a_{i-1} \neq a_i$$$.

К сожалению, ваш забор может быть не великим. Но вы можете это исправить! Вы можете увеличить длину $$$i$$$-й доски на $$$1$$$, но за это вам придется заплатить $$$b_i$$$ рублей. Длину каждой доски можно увеличивать любое количество раз (в том числе, можно не увеличивать её длину совсем).

Посчитайте минимальное количество рублей, которое вам нужно потратить, для того чтобы сделать забор великим снова!

Вам нужно ответить на $$$q$$$ независимых запросов.

Входные данные

Первая строка содержит число $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — количество запросов.

Первая строка каждого запроса содержит число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество досок в заборе.

Следующие $$$n$$$ строк каждого запроса содержат описание досок.$$$i$$$-я строка содержит два числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — длину $$$i$$$-й доски и цену за увеличение её длины на $$$1$$$, соответственно.

Гарантируется, что сумма $$$n$$$ по всем запросам не превосходит $$$3 \cdot 10^5$$$.

Так же гарантируется, что ответ не превосходит $$$10^{18}$$$.

Выходные данные

На каждый запрос выведите число в отдельной строке — минимальное количество рублей, которое вам нужно потратить, для того чтобы сделать забор великим.

Пример
Входные данные
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
Примечание

В первом запросе вам нужно увеличить длину второй доски на $$$2$$$. Тогда всего вы потратите $$$2 \cdot b_2 = 2$$$ рублей.

Во втором запросе вам нужно увеличить длину первой доски на $$$1$$$ и длину третьей доски на $$$1$$$. Таким образом, вы потратите $$$1 \cdot b_1 + 1 \cdot b_3 = 9$$$ рублей.

В третьем тестовом примере забор великий изначально, поэтому вам не нужно тратить деньги.