Hoán vị trộn

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 số là các số nguyên dương, không nhất thiết phân biệt, được lấy từ tập $\{1,2,\dots ,n\}$.

Đối với hai dãy đã cho, ta có thể thực hiện phép biến đổi sau đây: chọn hai chỉ số $i$ và $j$ với $1\le i\le j\le n$, sau đó hoán đổi hai dãy con $a_i,a_{i+1},\dots ,a_j$ và $b_i,b_{i+1},\dots ,b_j$ của hai dãy cho nhau, ta thu được hai dãy mới:

$$(a_1,a_2,\dots ,a_{i-1},b_i,b_{i+1},\dots ,b_j,a_{j+1},a_{j+2},\dots ,a_n)$$

và:

$$(b_1,b_2,\dots ,b_{i-1},a_i,a_{i+1},\dots ,a_j,b_{j+1},b_{j+2},\dots ,b_n).$$

Như vậy, phép biến đổi nêu trên được xác định bởi cặp hai chỉ số $(i,j)$.

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

Yêu cầu: Hãy xác định xem có thể thu được hoán vị trộn bởi bao nhiêu cách. Hai cách là khác nhau nếu cặp chỉ số $(i,j)$ khác nhau (kể cả khi các dãy thu được giống nhau). Mỗi cách chỉ được tính một lần, kể cả khi cả hai dãy thu được đều là hoán vị.

Dữ liệu vào

Dữ liệu gồm nhiều test có cấu trúc như sau:

• Dòng đầu tiên là số $t$ $(1\le t\le 5)$ là số test. Sau đó là các test, mỗi test gồm:
  • Dòng thứ nhất chứa số nguyên $n$ $(1\le n\le 2·{10}^5)$.
  • Dòng thứ hai chứa dãy số $a_1,a_2,\dots ,a_n$ $(1\le a_i\le n)$.
  • Dòng thứ ba chứa dãy số $b_1,b_2,\dots ,b_n$ $(1\le b_i\le n)$.

Dữ liệu ra

Gồm $t$ dòng, mỗi dòng một số nguyên, tương ứng là số cách khác nhau có thể thu được hoán vị trộn nhờ thực hiện phép biến đổi đã nêu đối với hai dãy tương ứng trong dữ liệu vào.

Ràng buộc

• $1\le t\le 5$.
• $1\le n\le 2·{10}^5$.
• $1\le a_i,b_i\le n$.

Subtasks

• Subtask 1 ($30\%$ số test, ứng với $30\%$ số điểm): $n\le 100$.
• Subtask 2 ($30\%$ số test khác, ứng với $30\%$ số điểm): $n\le 5000$.
• Subtask 3 ($40\%$ số test còn lại, ứng với $40\%$ số điểm): $n\le 2·{10}^5$.

Bài được chấm theo từng test, mỗi test có cùng số điểm.

Ví dụ