Занятой Бобёр украшает новогоднюю ёлку, но у него есть странные предпочтения относительно того, какие цвета использовать.

Рассмотрим раскраску вершин дерева в два цвета: красный и зелёный.

В раскраске связную компоненту зелёных вершин назовём крутой, если с этой компонентой граничит не более двух красных вершин. Для дерева $t$ пусть $f(t)$ — это максимальное количество крутых компонент при любой раскраске $t$.

Имеется дерево $t$, изначально содержащее только одну вершину, обозначенную как вершина $1$. Выполните $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$-я строка содержит значение $f(t)$ после $i$-го запроса.

Подзадачи

• ($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$.