You have a fence consisting of $n$ vertical boards. The width of each board is $1$. The height of the $i$-th board is $a_i$. You think that the fence is great if there is no pair of adjacent boards having the same height. More formally, the fence is great if and only if for all indices from $2$ to $n$, the condition $a_{i-1} \neq a_i$ holds.

Unfortunately, it is possible that now your fence is not great. But you can change it! You can increase the length of the $i$-th board by $1$, but you have to pay $b_i$ rubles for it. The length of each board can be increased any number of times (possibly, zero).

Calculate the minimum number of rubles you have to spend to make the fence great again!

You have to answer $q$ independent queries.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.

The first line of each query contains one integers $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of boards in the fence.

The following $n$ lines of each query contain the descriptions of the boards. The $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$) — the length of the $i$-th board and the price for increasing it by $1$, respectively.

It is guaranteed that sum of all $n$ over all queries not exceed $3 \cdot 10^5$.

It is guaranteed that answer to each query will not exceed $10^{18}$.


-----Output-----

For each query print one integer — the minimum number of rubles you have to spend to make the fence great.


-----Example-----
Input
3
3
2 4
2 1
3 5
3
2 3
2 10
2 6
4
1 7
3 3
2 6
1000000000 2

Output
2
9
0



-----Note-----

In the first query you have to increase the length of second board by $2$. So your total costs if $2 \cdot b_2 = 2$.

In the second query you have to increase the length of first board by $1$ and the length of third board by $1$. So your total costs if $1 \cdot b_1 + 1 \cdot b_3 = 9$.

In the third query the fence is great initially, so you don't need to spend rubles.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '\'\'\' CODED WITH LOVE BY SATYAM KUMAR \'\'\'\n\nfrom sys import stdin, stdout\nimport heapq\nimport cProfile, math\nfrom collections import Counter, defaultdict, deque\nfrom bisect import bisect_left, bisect, bisect_right\nimport itertools\nfrom copy import deepcopy\nfrom fractions import Fraction\nimport sys, threading\nimport operator as op\nfrom functools import reduce\nimport sys\n\nsys.setrecursionlimit(10 ** 6)  # max depth of recursion\nthreading.stack_size(2 ** 27)  # new thread will get stack of such size\nfac_warm_up = False\nprintHeap = str()\nmemory_constrained = False\nP = 10 ** 9 + 7\n\n\nclass MergeFind:\n    def __init__(self, n):\n        self.parent = list(range(n))\n        self.size = [1] * n\n        self.num_sets = n\n        self.lista = [[_] for _ in range(n)]\n\n    def find(self, a):\n        to_update = []\n        while a != self.parent[a]:\n            to_update.append(a)\n            a = self.parent[a]\n        for b in to_update:\n            self.parent[b] = a\n        return self.parent[a]\n\n    def merge(self, a, b):\n        a = self.find(a)\n        b = self.find(b)\n        if a == b:\n            return\n        if self.size[a] < self.size[b]:\n            a, b = b, a\n        self.num_sets -= 1\n        self.parent[b] = a\n        self.size[a] += self.size[b]\n        self.lista[a] += self.lista[b]\n\n    def set_size(self, a):\n        return self.size[self.find(a)]\n\n    def __len__(self):\n        return self.num_sets\n\n\ndef display(string_to_print):\n    stdout.write(str(string_to_print) + "\\n")\n\n\ndef prime_factors(n):  # n**0.5 complex\n    factors = dict()\n    for i in range(2, math.ceil(math.sqrt(n)) + 1):\n        while n % i == 0:\n            if i in factors:\n                factors[i] += 1\n            else:\n                factors[i] = 1\n            n = n // i\n    if n > 2:\n        factors[n] = 1\n    return (factors)\n\n\ndef all_factors(n):\n    return set(reduce(list.__add__,\n                      ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))\n\n\ndef fibonacci_modP(n, MOD):\n    if n < 2: return 1\n    return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(\n        fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD\n\n\ndef factorial_modP_Wilson(n, p):\n    if (p <= n):\n        return 0\n    res = (p - 1)\n    for i in range(n + 1, p):\n        res = (res * cached_fn(InverseEuler, i, p)) % p\n    return res\n\n\ndef binary(n, digits=20):\n    b = bin(n)[2:]\n    b = \'0\' * (digits - len(b)) + b\n    return b\n\n\ndef is_prime(n):\n    """Returns True if n is prime."""\n    if n < 4:\n        return True\n    if n % 2 == 0:\n        return False\n    if n % 3 == 0:\n        return False\n    i = 5\n    w = 2\n    while i * i <= n:\n        if n % i == 0:\n            return False\n        i += w\n        w = 6 - w\n    return True\n\n\ndef generate_primes(n):\n    prime = [True for i in range(n + 1)]\n    p = 2\n    while p * p <= n:\n        if prime[p]:\n            for i in range(p * 2, n + 1, p):\n                prime[i] = False\n        p += 1\n    return prime\n\n\nfactorial_modP = []\n\n\ndef warm_up_fac(MOD):\n    nonlocal factorial_modP, fac_warm_up\n    if fac_warm_up: return\n    factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]\n    for i in range(2, fac_warm_up_size):\n        factorial_modP[i] = (factorial_modP[i - 1] * i) % MOD\n    fac_warm_up = True\n\n\ndef InverseEuler(n, MOD):\n    return pow(n, MOD - 2, MOD)\n\n\ndef nCr(n, r, MOD):\n    nonlocal fac_warm_up, factorial_modP\n    if not fac_warm_up:\n        warm_up_fac(MOD)\n        fac_warm_up = True\n    return (factorial_modP[n] * (\n            (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD)) % MOD)) % MOD\n\n\ndef test_print(*args):\n    if testingMode:\n        print(args)\n\n\ndef display_list(list1, sep=" "):\n    stdout.write(sep.join(map(str, list1)) + "\\n")\n\n\ndef display_2D_list(li):\n    for i in li:\n        print(i)\n\n\ndef prefix_sum(li):\n    sm = 0\n    res = []\n    for i in li:\n        sm += i\n        res.append(sm)\n    return res\n\n\ndef get_int():\n    return int(stdin.readline().strip())\n\n\ndef get_tuple():\n    return list(map(int, stdin.readline().split()))\n\n\ndef get_list():\n    return list(map(int, stdin.readline().split()))\n\n\nmemory = dict()\n\n\ndef clear_cache():\n    nonlocal memory\n    memory = dict()\n\n\ndef cached_fn(fn, *args):\n    nonlocal memory\n    if args in memory:\n        return memory[args]\n    else:\n        result = fn(*args)\n        memory[args] = result\n        return result\n\n\ndef ncr(n, r):\n    return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))\n\n\ndef binary_search(i, li):\n    fn = lambda x: li[x] - x // i\n    x = -1\n    b = len(li)\n    while b >= 1:\n        while b + x < len(li) and fn(b + x) > 0:  # Change this condition 2 to whatever you like\n            x += b\n        b = b // 2\n    return x\n\n\n# -------------------------------------------------------------- MAIN PROGRAM\n\n\nTestCases = True\nfac_warm_up_size = 10 ** 5 + 100\noptimise_for_recursion = False  # Can not be used clubbed with TestCases WHen using recursive functions, use Python 3\n\n\ndef main():\n    n = get_int()\n    lengths = []\n    costs = []\n\n    for _ in range(n):\n        a, b = get_tuple()\n        lengths.append(a)\n        costs.append(b)\n    dp = [[0, costs[0], 2*costs[0]]]\n    for i in range(1, n):\n        kt = [10 ** 20] * 3\n        for k in range(3):\n            for j, ele in enumerate(dp[-1]):\n                if lengths[i-1]+j!=lengths[i]+k:\n                    kt[k] = min(kt[k], ele+costs[i]*k)\n        dp.append(kt)\n    #print(dp)\n    print(min(dp[-1]))\n\n\n# --------------------------------------------------------------------- END=\n\n\nif TestCases:\n    for i in range(get_int()):\n        main()\nelse:\n    main() if not optimise_for_recursion else threading.Thread(target=main).start()\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: