Trộn dãy

Cho hai dãy số nguyên dương độ dài \(n\):
\(a=(a_1,a_2,\dots,a_n)\) và \(b=(b_1,b_2,\dots,b_n)\). Biết rằng các phần tử của hai dãy đều là các số nguyên dương thuộc tập \(\{1,2,\dots,n\}\).

Ta định nghĩa một phép biến đổi như sau: chọn hai chỉ số \(i\) và \(j\) thỏa \(1\le i\le j\le n\), rồi hoán đổi hai đoạn con
$
a_i,a_{i+1},\dots,a_j
\quad\text{và}\quad
b_i,b_{i+1},\dots,b_j
$
giữa hai dãy. Sau phép hoán đổi thu được hai dãy mới:
$
a' = (a_1,\dots,a_{i-1},\,b_i,\dots,b_j,\,a_{j+1},\dots,a_n),
$
$
b' = (b_1,\dots,b_{i-1},\,a_i,\dots,a_j,\,b_{j+1},\dots,b_n).
$

Nếu sau khi thực hiện phép biến đổi như trên có ít nhất một trong hai dãy \(a'\) hoặc \(b'\) là một hoán vị của tập \(\{1,2,\dots,n\}\) thì ta nói phép biến đổi đó tạo ra một hoán vị trộn.

Yêu cầu: Với mỗi test, hãy xác định có bao nhiêu cặp \((i,j)\) khác nhau sẽ tạo ra hoán vị trộn theo định nghĩa trên.

\InputFile

• Dòng đầu tiên là số nguyên \(t\) (\(t\le 5\)) --- số test.

• Mỗi test gồm ba dòng:

• Dòng đầu của test chứa số nguyên \(n\) (\(1\le n \le 2\cdot 10^5\)).

• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,\dots,a_n\) (mọi \(a_i \le n\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(b_1,b_2,\dots,b_n\) (mọi \(b_i \le n\)).

\OutputFile

• Ghi ra \(t\) dòng, mỗi dòng là một số nguyên --- số cách (số cặp \((i,j)\) khác nhau) có thể tạo ra hoán vị trộn cho test tương ứng.

\Scoring

• Subtask 1 (30%): \(n \le 100\).
• Subtask 2 (30%): \(n \le 5000\).
• Subtask 3 (40%): không có ràng buộc gì thêm.

Example

2
6
3 2 1 4 4 5
2 3 3 4 6 5
2
1 2
1 2

8
3