Problem Statement

For an undirected tree with $N$ vertices named $1,2,\ldots,N$, a permutation $X$ of $(1,2,\ldots,N)$ is called a Pruning Order if it satisfies the following condition.

• For $i = 1,2,\ldots,N$ in this order, delete vertex $X_i$ and all edges having vertex $X_i$ as an endpoint. Here, for every $i = 1,2,\ldots,N - 1$, vertex $X_i$ is a leaf immediately before it is deleted.

You are given permutations $P,Q,R$ of $(1,2,\ldots,N)$. Find the number, modulo $M$, of undirected trees with vertices named $1,2,\ldots,N$ such that $P,Q,R$ are all Pruning Orders.

There are $T$ test cases in total.

Constraints

• $1 \le T \le 10^5$
• $1 \le N \le 10^5$
• $2 \le M \le 10^9$
• $P,Q,R$ are permutations of $(1,2,\ldots,N)$
• The sum of $N$ over all test cases is at most $10^5$
• All input values are integers

Input

The input is given from standard input in the following format. Here, $\mathrm{case}_i$ is the $i$-th test case.

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

Each test case is given in the following format.

$N \ M$
$P_{1} \ P_2 \ \ldots \ P_{N}$
$Q_{1} \ Q_2 \ \ldots \ Q_{N}$
$R_{1} \ R_2 \ \ldots \ R_{N}$

Output

Print $T$ lines. The $i$-th line should contain the answer for $\text{case}_i$.

Sample

3
4 5
1 4 2 3
3 1 2 4
4 1 3 2
3 2
1 2 3
1 2 3
2 3 1
20 998244353
18 14 17 15 6 9 19 12 16 13 10 11 4 20 7 5 8 3 1 2
18 20 7 17 19 3 13 15 6 2 5 14 4 11 10 16 9 1 8 12
20 14 7 18 12 15 16 11 10 3 9 19 8 17 2 4 1 6 5 13

1
1
44236800