Vòng tròn quái vật

Có $n$ con quái vật đứng thành một vòng tròn, được đánh số theo chiều kim đồng hồ từ $1$ đến $n$. Ban đầu con quái vật thứ $i$ có $a_i$ máu.

Bạn tiêu diệt quái vật bằng cách bắn. Mỗi phát bắn tốn đúng một viên đạn và làm giảm $1$ máu của con quái vật bị nhắm tới. Khi máu của một con quái vật $i$ giảm xuống $0$ hoặc thấp hơn, nó chết và nổ, gây $b_i$ sát thương cho con quái vật kế tiếp (con $i+1$ nếu $i<n$, hoặc con $1$ nếu $i=n$). Nếu con kế tiếp đã chết thì không có gì xảy ra. Nếu vụ nổ giết con kế tiếp, con đó cũng nổ, gây sát thương cho con sau nó và có thể kích hoạt một dây chuyền nổ, cứ như vậy tiếp tục.

Hãy tính số viên đạn ít nhất cần bắn để tiêu diệt toàn bộ $n$ con quái vật trong vòng tròn.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $T$ là số lượng bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa một số nguyên $n$ là số quái vật.
  • $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$ là các tham số của con quái vật thứ $i$ trong vòng tròn.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là số viên đạn ít nhất cần bắn để tiêu diệt toàn bộ quái vật.

Ràng buộc

• $1\le T\le 150000$
• $2\le n\le 300000$
• $1\le a_i,b_i\le {10}^{12}$
• Tổng số quái vật trong tất cả các bộ dữ liệu không vượt quá $300000$.

Ví dụ