Đường đi tam giác

Xét một tam giác vô hạn gồm các tầng. Đánh số các tầng từ $1$ bắt đầu từ đỉnh tam giác (từ trên xuống dưới). Tầng thứ $k$ chứa $k$ điểm, đánh số từ trái sang phải. Mỗi điểm được mô tả bởi cặp số $(r,c)$ với $1\le c\le r$, trong đó $r$ là số tầng và $c$ là số thứ tự điểm trong tầng đó.

Từ mỗi điểm $(r,c)$ có hai cạnh có hướng đi xuống $(r+1,c)$ và $(r+1,c+1)$, nhưng tại mỗi điểm chỉ có đúng một cạnh được kích hoạt:

• Nếu $r+c$ chẵn, cạnh đi tới $(r+1,c)$ được kích hoạt.
• Nếu $r+c$ lẻ, cạnh đi tới $(r+1,c+1)$ được kích hoạt.

Ban đầu bạn ở điểm $(1,1)$. Tại mỗi lượt bạn có thể thực hiện một trong hai thao tác:

• Đảo cạnh tại điểm $(r,c)$ hiện tại: thay cạnh kích hoạt hiện tại bằng cạnh còn lại. Thao tác này làm chi phí đường đi tăng thêm $1$.
• Di chuyển từ điểm hiện tại theo cạnh đang được kích hoạt sang điểm kế tiếp. Thao tác này không tốn chi phí.

Cho dãy $n$ điểm $(r_1,c_1),(r_2,c_2),\dots ,(r_n,c_n)$ phân biệt. Hãy tìm chi phí nhỏ nhất của đường đi xuất phát từ $(1,1)$ và đi qua tất cả $n$ điểm theo thứ tự bất kỳ.

Dữ liệu đảm bảo luôn tồn tại ít nhất một cách đi qua đủ $n$ điểm.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ($1\le t\le {10}^4$) — số bộ test.

Với mỗi bộ test:

• Dòng đầu chứa số nguyên $n$ ($1\le n\le 2·{10}^5$) — số điểm cần đi qua.
• Dòng thứ hai chứa $n$ số nguyên $r_1,r_2,\dots ,r_n$ ($1\le r_i\le {10}^9$).
• Dòng thứ ba chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$ ($1\le c_i\le r_i$).

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

Dữ liệu ra

Với mỗi bộ test, in ra một dòng chứa chi phí nhỏ nhất của đường đi.

Ví dụ