Tahp is a boy fascinated by the beauty of the overlapping mountain ranges. One day, while playing with his favorite sequence of numbers, he suddenly came up with an interesting idea about how to arrange the elements in the sequence to form the shape of a mountain.

Let Tahp's favorite sequence be ~a~ of length ~n~. He calls ~a~ a mountain array if there exists an integer ~k~ satisfying all of the following conditions:

• ~1 \le k \le n~

• ~a_i \le a_{i+1}~ for all ~1 \le i < k~

• ~a_i \le a_{i-1}~ for all ~k < i \le n~

In other words, the sequence will not decrease from position ~1~ to ~k~, and then not increase from position ~k~ to ~n~ afterwards, resembling the shape of a mountain.

It is clear that not every sequence is a mountain array, so Tahp needs to swap two consecutive elements in the given sequence multiple times to transform it into a mountain array. He defines the mountain difference of a sequence as the minimum number of consecutive swaps needed to transform that sequence into a mountain array.

Tahp writes down all the distinct permutations~^*~ of the sequence ~a~, and then selects two special sequences ~l~ and ~h~. Now, he wants to calculate the total mountain difference of all distinct permutations ~p~ of ~a~ that satisfy ~l \le p \le h~ in lexicographic order~^\dagger~.

Your task is to help Tahp calculate the total mountain difference of all distinct permutations that satisfy the above condition. Since the result can be very large, you only need to provide the remainder after dividing it by ~998\,244\,353~.

——————————————-

~^*~ A permutation of a sequence is another sequence that has the same set of elements (including duplicates, if any), but can be arranged in any order. For example, ~[1, 2, 2, 3]~, ~[2, 3, 1, 2]~, and ~[2, 2, 1, 3]~ are some of the permutations of ~[3, 2, 1, 2]~, but ~[2, 4, 3, 1]~, ~[2, 1, 2]~, and ~[1, 1, 2, 3]~ are not. Two permutations are considered different if there exists a position where the value of the element in this permutation differs from the value of the element at the same position in the other permutation.

~^\dagger~ Given two integer sequences ~a = [a_1, a_2, \ldots, a_n]~ and ~b = [b_1, b_2, \ldots, b_n]~. We say that ~a~ is less than or equal to ~b~ in lexicographic order (denoted ~a \le b~) if ~a_i = b_i~ for all ~1 \le i \le n~, or if ~a_j < b_j~ where ~j~ is the smallest index satisfying ~a_j \neq b_j~.

Input

The first line contains an integer ~t~ (~1 \le t \le 10~) — the number of test cases. The description of each test case is as follows.

The first line contains a single integer ~n~ (~1 \le n \le 1000~) — the length of Tahp's favorite sequence.

The second line contains ~n~ integers ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le n~) — Tahp's favorite sequence.

The third line contains ~n~ integers ~l_1, l_2, \dots, l_n~ (~1 \le l_i \le n~) — the selected sequence ~l~.

The last line contains ~n~ integers ~h_1, h_2, \dots, h_n~ (~1 \le h_i \le n~) — the selected sequence ~h~.

It is guaranteed that ~l~ and ~r~ are permutations of ~a~, and ~l \le h~ in lexicographic order.

Output

Print ~t~ lines, where the ~i~-th line contains a single integer which is the result for the ~i~-th test case after taking the remainder with ~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

In the first test case, there are ~7~ distinct permutations that satisfy as follows:

• ~[2, 1, 3, 2]~ has a mountain difference of ~1~: ~[\underline{2, 1}, 3, 2] \rightarrow [1, 2, \hat{3}, 2]~

• ~[2, 2, 1, 3]~ has a mountain difference of ~1~: ~[2, 2, \underline{1, 3}] \rightarrow [2, 2, \hat{3}, 1]~

• ~[2, 2, 3, 1]~ has a mountain difference of ~0~: ~[2, 2, \hat{3}, 1]~

• ~[2, 3, 1, 2]~ has a mountain difference of ~1~: ~[2, 3, \underline{1, 2}] \rightarrow [2, \hat{3}, 2, 1]~

• ~[2, 3, 2, 1]~ has a mountain difference of ~0~: ~[2, \hat{3}, 2, 1]~

• ~[3, 1, 2, 2]~ has a mountain difference of ~1~: ~[\underline{3, 1}, 2, 2] \rightarrow [1, \hat{3}, 2 , 2]~

• ~[3, 2, 1, 2]~ has a mountain difference of ~1~: ~[3, 2, \underline{1, 2}] \rightarrow [\hat{3}, 2, 2, 1]~

The total mountain difference is ~1 + 1 + 0 + 1 + 0 + 1 + 1 = 5~