Busy Beaver はクリスマスツリーの飾り付けをしていますが、使う色について少し変わったこだわりを持っています。

木の頂点を赤と緑の2色で塗り分けることを考えます。

ある塗り方において、緑色の頂点からなる連結成分が、高々2つの赤色の頂点と隣接しているとき、その連結成分を「クール」と呼ぶことにします。木 $t$ に対して、$f(t)$ をその木におけるクールな連結成分の数の最大値とします。

最初は頂点1のみを含む木 $t$ があります。$N$ 回のクエリを行います。$i$ 番目のクエリでは、頂点 $a_i$ に新しい葉頂点を追加します。変数 $X \in \{0, 1\}$ に応じて、以下の2種類のテストケースがあります。

• $X = 0$ の場合、すべてのクエリが完了した後の $f(t)$ を出力してください。
• $X = 1$ の場合、各クエリの後の $f(t)$ を出力してください。

入力

複数のテストケースが含まれます。入力ファイルの先頭には、テストケースの数 $T$ とテストの種類 $X$ ($1 \le T \le 4\cdot 10^4$, $X \in \{0, 1\}$) が与えられます。

各テストケースの1行目には、整数 $N$ ($1 \le N \le 2 \cdot 10^5$) が与えられます。

2行目には、$N$ 個の整数 $a_1, \dots, a_N$ ($1 \le a_i \le i$) が与えられます。

すべてのテストケースにおける $N$ の総和は $4 \cdot 10^5$ を超えないことが保証されています。

出力

$X = 0$ の場合、各テストケースについて、最終的な木に対する $f(t)$ を1行で出力してください。

$X = 1$ の場合、各テストケースについて $N$ 行出力してください。$i$ 行目には、$i$ 番目のクエリ後の $f(t)$ の値を出力してください。

小課題

• ($25$ 点) $X = 0$。
• ($30$ 点) 各 $a_i$ は $[1, i]$ から一様ランダムに選ばれる。
• ($45$ 点) 追加の制約なし。

入出力例

入力 1

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

出力 1

3
5

入力 2

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

出力 2

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

注記

入出力例 1 の説明

1つ目のテストケースでは、頂点 $1, 2, 4, 5$ を緑色に塗ることができます（最初から頂点が1つあるため、頂点は合計 $N + 1 = 5$ 個存在することに注意してください）。このとき、$\{1, 2\}$, $\{4\}$, $\{5\}$ がクールな連結成分となります。

2つ目のテストケースでは、頂点 $1, 4, 5, 6, 8, 9$ を緑色に塗ることができます。このとき、$\{1\}$, $\{4\}$, $\{5, 8\}$, $\{6\}$, $\{9\}$ がクールな連結成分となります。

入出力例 2 の説明

このサンプルは1つ目と同じ木を使用していますが、$X = 1$ のタイプです。