You are given two arrays $A$ = $A_{1}, A_{2}, \ldots, A_{N}$ and $B$ = $B_{1}, B_{2}, \ldots, B_{N}$. We want to make these two arrays identical. That is, for each $1 ≤ i ≤ N$, we want to make $A_{i}$ = $B_{i}$. To do this, we are allowed to make many operations of the following type:

In a single operation, we choose two integers $x$ and $y$, and replace all the occurrences of $x$ in both the arrays with $y$. This operation is denoted by $(x, y)$. Notice that regardless of the number of characters replaced, it will still be counted as a single operation.

A sequence of operations $((x_{1}, y_{1}), (x_{2}, y_{2}), \ldots, (x_{m}, y_{m}))$ is said to be optimal, if after performing these operations in the given order, both arrays $A$ and $B$ are identical, and there is no sequence with fewer operations which can achieve the same.

You will also be given an integer $K$ which will either be $1$ or $2$. If $K = 1$, you need to output the minimum number of operations needed to make the two arrays identical. If $K = 2$, in addition to the minimum number of operations, you should also output the number of different optimal sequences. As this number could be huge, output it modulo $10^{9} + 7$.

------ Input: ------

The first line of the input contains a single integer, $T$, which is the number of testcases. The description of each testcase follows.
The first line of each testcase contains two integers: $N$, and $K$.
The next line contains $N$ integers: $A_{1}, A_{2}, \ldots, A_{N}$.
The next line contains $N$ integers: $B_{1}, B_{2}, \ldots, B_{N}$.

------ Output: ------
You need to output a single line for each testcase.
If $K = 1$, then that corresponding line should contain a single integer, which is the minimum number of operations needed.
If $K = 2$, then that corresponding line should contain two integers, the minimum number of operations needed and the number of optimal sequences modulo $10^{9} + 7$.

------ Constraints ------
$1 ≤ T ≤ 5$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ 2$
$1 ≤ A_{i}, B_{i} ≤ N$

------ Subtasks ------
16 points : $K = 1$
84 points : No further constraints.

----- Sample Input 1 ------
2
5 1
2 1 1 3 5
1 2 2 4 5
5 2
2 1 1 3 5
1 2 2 4 5
----- Sample Output 1 ------
2
2 8
----- explanation 1 ------
Testcase 1: The arrays are initially $(2, 1, 1, 3, 5)$ and $(1, 2, 2, 4, 5)$. Consider the sequence of operations $((1, 2), (3, 4))$. In the first operation all the $1$s are converted into $2$s. So, the arrays will now be $(2, 2, 2, 3, 5)$ and $(2, 2, 2, 4, 5)$. In the second operation all the $3$s are converted into $4$s. So, the arrays will now be $(2, 2, 2, 4, 5)$ and $(2, 2, 2, 4, 5)$. We have made the two arrays identical in two operations, and you can check that you cannot do better. Hence the output is $2$.

Testcase 2: The arrays are the same, and hence the first integer is the same. Now we need to also find the number of optimal sequences. They are listed below:

• $((1, 2), (3, 4))$
• $((1, 2), (4, 3))$
• $((2, 1), (3, 4))$
• $((2, 1), (4, 3))$
• $((3, 4), (1, 2))$
• $((3, 4), (2, 1))$
• $((4, 3), (1, 2))$
• $((4, 3), (2, 1))$

Since there are eight optimal sequences, the second integer is $8$.

见题面

见题面