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 là 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.

Input

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

• Dòng đầu tiên là số ~t~ ~(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 \cdot 10^5)~.

  • Dòng thứ hai chứa dãy số ~a_1,a_2,\dots,a_n~ ~(a_i \le n)~.

  • Dòng thứ ba chứa dãy số ~b_1,b_2,\dots,b_n~ ~(b_i \le n)~.

Output

Gồ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.

Scoring

Sample Input 1

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

Sample Output 1

8
3