Sửa hàng rào cho đẹp

Bạn có một hàng rào gồm $n$ tấm ván dựng đứng. Mỗi tấm ván có chiều rộng bằng $1$. Tấm ván thứ $i$ có chiều cao $a_i$.

Hàng rào được gọi là đẹp nếu không có hai tấm ván kề nhau nào có cùng chiều cao. Nói cách khác, với mọi $i$ từ $2$ đến $n$, phải có $a_{i-1}\ne a_i$.

Ban đầu hàng rào có thể chưa đẹp, nhưng bạn có thể chỉnh sửa nó. Bạn có thể tăng chiều cao của tấm ván thứ $i$ thêm $1$ đơn vị, nhưng phải trả $b_i$ rúp cho mỗi lần tăng. Mỗi tấm ván có thể được tăng chiều cao nhiều lần tùy ý (kể cả không tăng lần nào).

Hãy tính số rúp ít nhất bạn phải chi để hàng rào trở nên đẹp.

Bạn phải trả lời $q$ truy vấn độc lập.

Dữ liệu vào

Dòng đầu chứa số nguyên $q$ ($1\le q\le 3·{10}^5$) — số truy vấn.

Với mỗi truy vấn:

• Dòng đầu chứa số nguyên $n$ ($1\le n\le 3·{10}^5$) — số tấm ván.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$ ($1\le a_i,b_i\le {10}^9$) — chiều cao ban đầu của tấm ván thứ $i$ và giá tiền để tăng chiều cao tấm ván đó thêm $1$.

Tổng $n$ trên tất cả truy vấn không vượt quá $3·{10}^5$.

Đáp án của mỗi truy vấn được đảm bảo không vượt quá ${10}^{18}$.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng số rúp ít nhất cần chi để hàng rào đẹp.

Ví dụ