Busy Beaver는 크리스마스 트리를 장식하고 있지만, 사용할 색상에 대해 몇 가지 독특한 취향을 가지고 있습니다.

트리의 정점을 빨간색과 초록색, 두 가지 색으로 칠하는 경우를 생각해 봅시다.

색칠된 상태에서, 초록색 정점들로 이루어진 연결 성분이 인접한 빨간색 정점과 최대 두 개 이하로 연결되어 있다면 이를 멋진(cool) 성분이라고 부릅니다. 트리 $t$에 대하여, $f(t)$를 $t$의 모든 가능한 색칠 방법 중 멋진 성분의 최대 개수라고 정의합니다.

처음에는 정점 $1$ 하나만 존재하는 트리 $t$가 있습니다. $N$번의 쿼리를 수행합니다. $i$번째 쿼리에서는 정점 $a_i$에 새로운 잎 정점을 추가합니다. 변수 $X \in \{0, 1\}$에 따라 두 가지 유형의 테스트 케이스가 존재합니다.

• $X = 0$인 경우, 모든 쿼리가 완료된 후의 $f(t)$를 출력합니다.
• $X = 1$인 경우, 각 쿼리가 수행될 때마다 $f(t)$를 출력합니다.

입력

여러 개의 테스트 케이스가 존재합니다. 입력 파일은 테스트 케이스의 수 $T$와 테스트 유형 $X$ ($1 \le T \le 4\cdot 10^4$, $X \in \{0, 1\}$)로 시작합니다.

각 테스트 케이스의 첫 번째 줄에는 정수 $N$ ($1 \le N \le 2 \cdot 10^5$)이 주어집니다.

두 번째 줄에는 $N$개의 정수 $a_1, \dots, a_N$ ($1 \le a_i \le i$)이 주어집니다.

모든 테스트 케이스에 대한 $N$의 합은 $4 \cdot 10^5$를 넘지 않음이 보장됩니다.

출력

$X = 0$인 경우, 각 테스트 케이스에 대해 최종 트리의 $f(t)$ 값을 한 줄에 출력합니다.

$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, 2, 4, 5$를 초록색으로 칠할 수 있습니다(처음에 정점이 하나 있으므로 총 $N + 1 = 5$개의 정점이 있습니다). 이때 $\{1, 2\}$, $\{4\}$, $\{5\}$가 멋진 성분이 됩니다.

두 번째 테스트 케이스에서 정점 $1, 4, 5, 6, 8, 9$를 초록색으로 칠할 수 있습니다. 이때 $\{1\}$, $\{4\}$, $\{5, 8\}$, $\{6\}$, $\{9\}$가 멋진 성분이 됩니다.

예제 설명 2

이 예제는 첫 번째 예제와 동일한 트리를 사용하지만, $X = 1$ 유형입니다.