Moon has recently been playing a card game called Shadowverse. During the game, Moon thought of the following problem regarding shuffling. Suppose there are $n$ cards in a deck, and the $i$-th card is labeled $i$. We define a shuffling method as a permutation $X = \{x_1, x_2, \dots, x_n\}$, which means the card at the $i$-th position in the deck becomes the $x_i$-th card. Suppose Moon shuffles the deck $k$ times using the shuffling method $X$, and let the final result be a permutation $Y = \{y_1, y_2, \dots, y_n\}$, where $y_i$ represents the label of the $i$-th card after the shuffling is complete. Moon wants you to help him calculate how many valid shuffling methods $X$ exist such that after $k$ shuffles, the result is the permutation $Y$. Since the answer can be very large, you only need to output the answer modulo $998244353$.

Formally, consider two permutations $P = \{p_1, p_2, \dots, p_n\}$ and $Q = \{q_1, q_2, \dots, q_n\}$. We define the product of these two permutations as: $$P \times Q = \{q_{p_1}, q_{p_2}, \dots, q_{p_n}\}$$

The $k$-th power of a permutation $X$, denoted $X^k$, is the product of $k$ copies of the permutation $X$. Now, given a permutation $Y$ and a positive integer $k$, find the number of permutations $X$ that satisfy the equation $X^k = Y$, modulo $998244353$.

Input

The first line contains an integer $T$, representing the number of test cases. Each test case consists of two lines: The first line contains two positive integers $n$ and $k$, representing the length of the permutations $X$ and $Y$, and the number of shuffles, respectively. The second line contains $n$ distinct integers from $1$ to $n$, $\{y_1, y_2, \dots, y_n\}$, representing the permutation $Y$.

Output

Output $T$ lines, each containing a single integer representing the number of valid shuffling methods, modulo $998244353$.

Examples

Input 1

1
5 6
2 1 4 3 5

Output 1

2

Note

In the example, $X = [3, 4, 2, 1, 5]$ or $X = [4, 3, 1, 2, 5]$, for a total of two valid permutations.

Constraints

For all data, $1 \le n \le 3000$, $1 \le k \le 10^6$, $1 \le T \le 10$. For 20% of the data, $1 \le n, k \le 8$. For another 10% of the data, $1 \le n \le 8$. For another 30% of the data, $1 \le n \le 50$.