Tahp là một cậu bé say mê vẻ đẹp của những dãy núi hùng vĩ. Một ngày nọ, trong khi chơi với dãy số yêu thích của mình, cậu bỗng nảy ra một ý tưởng thú vị về cách sắp xếp các phần tử trong dãy để tạo thành hình dạng của một ngọn núi.

Giả sử dãy yêu thích của Tahp là ~a~ có độ dài ~n~. Cậu gọi ~a~ là một dãy núi nếu tồn tại một số nguyên ~k~ thỏa mãn tất cả các điều kiện sau:

• ~1 \le k \le n~

• ~a_i \le a_{i+1}~ cho tất cả ~1 \le i < k~

• ~a_i \le a_{i-1}~ cho tất cả ~k < i \le n~

Nói cách khác, dãy sẽ không giảm từ vị trí ~1~ đến ~k~, và sau đó sẽ không tăng từ vị trí ~k~ đến ~n~, giống như hình dạng của một ngọn núi.

Rõ ràng không phải mọi dãy đều là một dãy núi, vì vậy Tahp cần hoán đổi hai phần tử liên tiếp trong dãy đã cho nhiều lần để biến nó thành một dãy núi. Cậu định nghĩa độ chênh vênh của một dãy là số lần hoán đổi liên tiếp tối thiểu cần thiết để biến dãy đó thành một dãy núi.

Tahp ghi lại tất cả các hoán vị khác nhau~^*~ của dãy ~a~, và sau đó chọn hai dãy đặc biệt ~l~ và ~h~. Bây giờ, cậu muốn tính tổng độ chênh vênh của tất cả các hoán vị khác nhau ~p~ của ~a~ thỏa mãn ~l \le p \le h~ theo thứ tự từ điển~^\dagger~.

Nhiệm vụ của bạn là giúp Tahp tính tổng độ chênh vênh của tất cả các hoán vị khác nhau thỏa mãn điều kiện trên. Vì kết quả có thể rất lớn, bạn chỉ cần in phần dư sau khi chia đáp án cho ~998\,244\,353~.

—————————————

~^*~ Một hoán vị của một dãy là một dãy khác có cùng tập hợp các phần tử (bao gồm cả các phần tử trùng lặp, nếu có), nhưng có thể được sắp xếp theo bất kỳ thứ tự nào. Ví dụ, ~[1, 2, 2, 3]~, ~[2, 3, 1, 2]~, và ~[2, 2, 1, 3]~ là một số hoán vị của ~[3, 2, 1, 2]~, nhưng ~[2, 4, 3, 1]~, ~[2, 1, 2]~, và ~[1, 1, 2, 3]~ thì không. Hai hoán vị được coi là khác nhau nếu tồn tại một vị trí mà giá trị của phần tử trong hoán vị này khác với giá trị của phần tử ở cùng vị trí trong hoán vị còn lại.

~^\dagger~ Cho hai dãy số nguyên ~a = [a_1, a_2, \ldots, a_n]~ và ~b = [b_1, b_2, \ldots, b_n]~. Ta nói rằng ~a~ là nhỏ hơn hoặc bằng ~b~ theo thứ tự từ điển (ký hiệu ~a \le b~) nếu ~a_i = b_i~ cho tất cả ~1 \le i \le n~, hoặc nếu ~a_j < b_j~ với ~j~ là chỉ số nhỏ nhất thỏa mãn ~a_j \neq b_j~.

Input

Dòng đầu tiên chứa một số nguyên ~t~ (~1 \le t \le 10~) — số lượng test case. Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa một số nguyên duy nhất ~n~ (~1 \le n \le 1000~) — độ dài của dãy yêu thích của Tahp.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le n~) — dãy yêu thích của Tahp.

Dòng thứ ba chứa ~n~ số nguyên ~l_1, l_2, \dots, l_n~ (~1 \le l_i \le n~) — dãy được chọn ~l~.

Dòng cuối cùng chứa ~n~ số nguyên ~h_1, h_2, \dots, h_n~ (~1 \le h_i \le n~) — dãy được chọn ~h~.

Đảm bảo rằng ~l~ và ~r~ là hai hoán vị của ~a~, và ~l \le h~ theo thứ tự từ điển.

Output

In ra ~t~ dòng, trong đó dòng thứ ~i~ chứa một số nguyên duy nhất là kết quả cho test case thứ ~i~ sau khi chia lấy phần dư cho ~998\,244\,353~.

Scoring

Sample Input 1

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

Sample Output 1

5
146

Notes

Trong test case đầu tiên, có ~7~ hoán vị khác nhau thỏa mãn như sau:

• ~[2, 1, 3, 2]~ có độ chênh vênh là ~1~: ~[\underline{2, 1}, 3, 2] \rightarrow [1, 2, \hat{3}, 2]~

• ~[2, 2, 1, 3]~ có độ chênh vênh là ~1~: ~[2, 2, \underline{1, 3}] \rightarrow [2, 2, \hat{3}, 1]~

• ~[2, 2, 3, 1]~ có độ chênh vênh là ~0~: ~[2, 2, \hat{3}, 1]~

• ~[2, 3, 1, 2]~ có độ chênh vênh là ~1~: ~[2, 3, \underline{1, 2}] \rightarrow [2, \hat{3}, 2, 1]~

• ~[2, 3, 2, 1]~ có độ chênh vênh là ~0~: ~[2, \hat{3}, 2, 1]~

• ~[3, 1, 2, 2]~ có độ chênh vênh là ~1~: ~[\underline{3, 1}, 2, 2] \rightarrow [1, \hat{3}, 2 , 2]~

• ~[3, 2, 1, 2]~ có độ chênh vênh là ~1~: ~[3, 2, \underline{1, 2}] \rightarrow [\hat{3}, 2, 2, 1]~

Tổng độ chênh vênh là ~1 + 1 + 0 + 1 + 0 + 1 + 1 = 5~.