Chu trình đơn dài nhất

Cho $n$ chuỗi (chain). Chuỗi thứ $i$ gồm $c_i$ đỉnh được đánh số từ $1$ tới $c_i$ và có $c_i-1$ cạnh nối hai đỉnh liền kề: cạnh giữa đỉnh $j$ và đỉnh $j+1$ với mọi $1\le j<c_i$.

Ta hợp các chuỗi này lại thành một đồ thị duy nhất theo quy tắc:

1. Chuỗi đầu tiên được giữ nguyên.
2. Với mỗi $i\ge 2$: nối đỉnh $1$ của chuỗi $i$ với đỉnh $a_i$ của chuỗi $i-1$ bằng một cạnh.
3. Với mỗi $i\ge 2$: nối đỉnh $c_i$ (đỉnh cuối) của chuỗi $i$ với đỉnh $b_i$ của chuỗi $i-1$ bằng một cạnh.

Hai giá trị $a_1$ và $b_1$ được cho bằng $-1$ chỉ để giữ chỉ số nhất quán; chúng không tham gia xây dựng đồ thị.

Hãy tìm độ dài của chu trình đơn dài nhất trong đồ thị thu được. Độ dài của một chu trình được tính bằng số cạnh trên chu trình đó. Chu trình đơn là chu trình mà mỗi đỉnh trên đó được đi qua đúng một lần.

Dữ liệu vào

Dòng đầu chứa một số nguyên $t$ — số bộ dữ liệu.

Với mỗi bộ dữ liệu:

• Dòng thứ nhất chứa $n$ — số chuỗi.
• Dòng thứ hai chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$.
• Dòng thứ ba chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ với $a_1=-1$ và $1\le a_i\le c_{i-1}$ khi $i\ge 2$.
• Dòng thứ tư chứa $n$ số nguyên $b_1,b_2,\dots ,b_n$ với $b_1=-1$ và $1\le b_i\le c_{i-1}$ khi $i\ge 2$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng độ dài chu trình đơn dài nhất trong đồ thị tương ứng.

Ràng buộc

• $1\le t\le 1000$
• $2\le n\le {10}^5$
• $2\le c_i\le {10}^9$
• Tổng $n$ qua tất cả bộ dữ liệu không vượt quá ${10}^5$.

Ví dụ