F. Соревнование по программированию
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

BerSoft — крупнейшая IT-корпорация в Берляндии. В компании BerSoft работает $$$n$$$ сотрудников, пронумерованных от $$$1$$$ до $$$n$$$.

Первый сотрудник является руководителем компании и у него нет начальника. У каждого другого сотрудника $$$i$$$ есть ровно один непосредственный начальник $$$p_i$$$.

Сотрудник $$$x$$$ считается начальником (непосредственным или косвенным) сотрудника $$$y$$$, если выполняется одно из следующих условий:

  • сотрудник $$$x$$$ является непосредственным начальником сотрудника $$$y$$$;
  • сотрудник $$$x$$$ является начальником непосредственного начальника сотрудника $$$y$$$.

Структура BerSoft организована таким образом, что руководитель компании является начальником для каждого сотрудника.

Скоро будет проведено соревнование по программированию. Для этой цели будут созданы команды из двух человек. Однако, если в команде один сотрудник является начальником другого, им будет некомфортно вместе. Поэтому команды из двух человек должны быть созданы таким образом, что никто не был начальником для другого. Обратите внимание, что никакой сотрудник не может участвовать более чем в одной команде.

Ваша задача — посчитать максимально возможное количество команд в соответствии с вышеописанными правилами.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество сотрудников.

Вторая строка содержит $$$n-1$$$ целых чисел $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \le n$$$), где $$$p_i$$$ — номер непосредственного начальника $$$i$$$-го сотрудника.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимально возможное количество команд в соответствии с вышеописанными правилами.

Пример
Входные данные
6
4
1 2 1
2
1
5
5 5 5 1
7
1 2 1 1 3 3
7
1 1 3 2 2 4
7
1 2 1 1 1 3
Выходные данные
1
0
1
3
3
3
Примечание

В первом примере можно создать команду $$$(3, 4)$$$.

Во втором примере команда не может быть создана, потому что здесь всего $$$2$$$ сотрудника и один является начальником другого.

В третьем примере можно создать команду $$$(2, 3)$$$.

В четвертом примере можно создать команды $$$(2, 4)$$$, $$$(3, 5)$$$ и $$$(6, 7)$$$.

В пятом примере можно создать команды $$$(2, 3)$$$, $$$(6, 4)$$$ и $$$(5, 7)$$$.