Description

Little T has two sequences, $a$ and $b$, both of length $n$. Some elements in sequence $a$ are determined, while the rest are undetermined. Little T must fill in the undetermined elements. All elements in sequence $a$ must be integers between $1$ and $n$, inclusive.

After Little T determines all elements of sequence $a$, an operation is performed $m$ times. Each operation consists of two steps:

1. For all $i \in [1, n]$, set $b_i \gets a_i$.
2. For all $i \in [1, n]$, set $a_i \gets b_{b_i}$.

Little T wants to know, after all $m$ operations are completed, what is the maximum possible number of distinct elements in sequence $a$?

Input Format

This problem has multiple test cases.

The first line of the input contains an integer $T$, representing the number of test cases.

Then, $T$ test cases follow. For each test case:

• The first line contains two positive integers $n$ and $m$, representing the length of the sequences and the number of operations.
• The second line contains $n$ integers, representing the initial sequence $a$. If $a_i = 0$, the element at this position is undetermined. Otherwise, the element is determined.

Output Format

For each test case, output a single line containing a positive integer, which is the answer.

3
6 2
1 1 4 5 1 4
6 2
0 0 4 5 0 4
13 1
0 1 2 3 4 5 2 7 8 3 10 4 12

1
5
7

Hint

【Sample Explanation】

For the first sample case, the initial sequence $a$ is fully determined. After 2 operations, sequence $a$ becomes 1 1 1 1 1 1. The number of distinct elements is 1.

For the second sample case, Little T can set the initial sequence $a$ to 2 1 4 5 6 4. After 2 operations, sequence $a$ becomes 1 2 4 5 6 4. The number of distinct elements is 5.

【Constraints】

This problem uses bundled testing.

• Special Property: For all $i \in [1, n]$, $a_i \neq 0$.

For all test cases, it is guaranteed that: $1 \le T \le 5$, $1 \le n \le 10^6$, $1 \le m \le 10^9$, $0 \le a_i \le n$.

【Hints】

The input size may be large. Please use fast I/O methods. Please note the specific time and memory limits for this problem.