Busy Beaver is decorating a Christmas tree, but he has some strange preferences for what colors to use.

Consider a coloring of the vertices of a tree, using two colors: red and green.

In a coloring, call a connected component of green vertices cool if at most two red vertices are adjacent to that component. For a tree $t$, let $f(t)$ be the maximum number of cool components in any coloring of $t$.

There is a tree $t$, initially only containing a single vertex, denoted vertex $1$. Perform $N$ queries; in the $i^{\text{th}}$ query, add a leaf vertex by attaching it to vertex $a_i$. There are two types of test cases, depending on a variable $X \in \{0, 1\}$:

• If $X = 0$, output $f(t)$ after all queries are completed.
• If $X = 1$, output $f(t)$ after each query.

Input

There are multiple test cases. The input file begins with $T$ and $X$ ($1 \le T \le 4\cdot 10^4$, $X \in \{0, 1\}$), the number of test cases and the test type respectively.

The first line of each test case contains an integer $N$ ($1 \le N \le 2 \cdot 10^5$).

The second line contains $N$ integers $a_1, \dots, a_N$ ($1 \le a_i \le i$).

It is guaranteed that the sum of $N$ over all test cases does not exceed $4 \cdot 10^5$.

Output

If $X = 0$, then for each test case, output $f(t)$ for the final tree on a single line.

If $X = 1$, then for each test case, output $N$ lines, the $i^{\text{th}}$ line being the value of $f(t)$ after the $i^{\text{th}}$ query.

Scoring

• ($25$ points) $X = 0$.
• ($30$ points) Each $a_i$ is chosen uniformly at random from $[1, i]$.
• ($45$ points) No additional constraints.

Examples

Input 1

2 0
4
1 2 3 3
8
1 2 3 2 3 6 5 7

Output 1

3
5

Input 2

2 1
4
1 2 3 3
8
1 2 3 2 3 6 5 7

Output 2

1
2
2
3
1
2
2
3
4
4
4
5

Note

Sample Explanation 1

For the first test case, we can color vertices $1$, $2$, $4$, and $5$ green (note that there are $N + 1 = 5$ vertices since there is already a vertex in the beginning). Then $\{1, 2\}$, $\{4\}$, and $\{5\}$ are cool components.

For the second test case, we can color vertices $1$, $4$, $5$, $6$, $8$, and $9$ green. Then $\{1\}$, $\{4\}$, $\{5, 8\}$, $\{6\}$, and $\{9\}$ are cool components.

Sample Explanation 2

This sample has the same trees as the first one, but is of type $X = 1$.