A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a vertex $v$ (different from root) is the previous to $v$ vertex on the shortest path from the root to the vertex $v$. Children of the vertex $v$ are all vertices for which $v$ is the parent.

You are given a rooted tree with $n$ vertices. The vertex $1$ is the root. Initially, all vertices are healthy.

Each second you do two operations, the spreading operation and, after that, the injection operation:

Spreading: for each vertex $v$, if at least one child of $v$ is infected, you can spread the disease by infecting at most one other child of $v$ of your choice.

Injection: you can choose any healthy vertex and infect it.

This process repeats each second until the whole tree is infected. You need to find the minimal number of seconds needed to infect the whole tree.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of the vertices in the given tree.

The second line of each test case contains $n - 1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i \le n$), where $p_i$ is the ancestor of the $i$-th vertex in the tree.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case you should output a single integer — the minimal number of seconds needed to infect the whole tree.


-----Examples-----

Input
5
7
1 1 1 2 2 4
5
5 5 1 4
2
1
3
3 1
6
1 1 1 1 1
Output
4
4
2
3
4


-----Note-----

The image depicts the tree from the first test case during each second.

A vertex is black if it is not infected. A vertex is blue if it is infected by injection during the previous second. A vertex is green if it is infected by spreading during the previous second. A vertex is red if it is infected earlier than the previous second.

Note that you are able to choose which vertices are infected by spreading and by injections.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Sorting

Greedy algorithms


Solutions:
from collections import defaultdict
counter = defaultdict(int)

def solve(a):
	for ai in a:
		counter[ai] += 1
	count = list(counter.values())
	num_level = len(count)
	count.sort()
	for i in range(num_level):
		count[i] = max(count[i] - i - 2, 0)
	L = 0
	R = max(count)
	if R == 0:
		return num_level + 1

	def check(k):
		b = count.copy()
		for i in range(len(b)):
			b[i] = max(b[i] - k, 0)
		if sum(b) <= k:
			return True
		return False
	while R - L > 1:
		mid = (R + L) // 2
		if check(mid):
			R = mid
		else:
			L = mid
	return num_level + 1 + R
for a in [*open(0)][2::2]:
	counter.clear()
	res = solve(a.split())
	print(res)


from collections import Counter
import heapq
numeroTestes = int(input())
results = []
for a in range(numeroTestes):
	vertices = int(input())
	pais = [int(t) for t in input().split()]
	counterPais = Counter(pais)
	l = []
	total = 0
	sorted_Values = sorted(counterPais.values(), reverse=True)
	for value in sorted_Values:
		tamanho = len(counterPais)
		va = tamanho + 1 - value - total
		if va < 0:
			heapq.heappush(l, va)
		total += 1
	cont = 0
	while l:
		va = -heapq.heappop(l)
		if va <= cont:
			break
		cont += 1
		heapq.heappush(l, -va + 1)
	results.append(cont + total + 1)
for r in results:
	print(r)


from collections import Counter

def calculate(nodes):
	common = Counter(nodes).most_common()
	secs = 0
	counts = []
	times = []
	for (elem, count) in common:
		times.append(count + secs)
		counts.append(count)
		secs += 1
	secs += 1
	while max(times) > secs:
		while times[0] > secs and (len(times) == 1 or times[0] >= times[1]):
			secs += 1
			times[0] -= 1
		for i in range(len(times)):
			if times[i] > secs and times[i] > times[0]:
				secs += 1
				times[i] -= 1
	print(secs)
cases = int(input())
for i in range(cases):
	input()
	calculate(input().split(' '))


import sys
input = sys.stdin.readline

def main():
	import heapq
	t = int(input())
	for _ in range(t):
		n = int(input())
		parent = [0] * (n + 1)
		a = list(map(int, input().split()))
		for i in range(n - 1):
			parent[a[i]] += 1
		(heap1, heap2) = ([], [])
		for i in parent:
			if i > 0:
				heapq.heappush(heap1, -i)
		heapq.heappush(heap1, -1)
		j = len(heap1)
		i = 0
		ans = 0
		while heap1:
			ans += 1
			cand = -heapq.heappop(heap1)
			if cand - (j - i) > 0:
				heapq.heappush(heap2, -(cand - (j - i)))
			i += 1
		(heap1, heap2) = (heap2, heap1)
		while heap1:
			ans += 1
			cand = -heapq.heappop(heap1)
			if cand - 2 > 0:
				heapq.heappush(heap2, -(cand - 2))
			while heap1:
				cand = -heapq.heappop(heap1)
				if cand - 1 > 0:
					heapq.heappush(heap2, -cand + 1)
			while heap2:
				cand = -heapq.heappop(heap2)
				heapq.heappush(heap1, -cand)
		sys.stdout.write(f'{ans}\n')
main()


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	groups = Counter(p)
	g = len(groups)
	time_needed = []
	infection_timer = 0
	for (_, group_size) in groups.most_common():
		time_needed.append(infection_timer + group_size)
		infection_timer += 1
	infection_timer += 1
	while infection_timer < max(time_needed):
		while (g == 1 or time_needed[0] >= time_needed[1]) and infection_timer < time_needed[0]:
			time_needed[0] -= 1
			infection_timer += 1
		if g > 1:
			for group_id in range(1, g):
				if time_needed[group_id] > time_needed[0] and infection_timer < time_needed[group_id]:
					time_needed[group_id] -= 1
					infection_timer += 1
	print(infection_timer)


import time
for _ in range(int(input())):
	n = int(input())
	a = [0] * (n + 1)
	a[0] = 1
	for i in list(map(int, input().split())):
		a[i] += 1
	try:
		a = [x for x in a if x > 0]
		a.sort(reverse=True)
		ans = len(a)
		for i in range(len(a)):
			a[i] -= len(a) - i
		a = [x for x in a if x > 0]
		while len(a) != 0:
			a.sort(reverse=True)
			a = [x - 1 for x in a]
			a[0] -= 1
			ans += 1
			a = [x for x in a if x > 0]
		print(ans)
	except Exception as e:
		print('Was exception: ')
		print(e)
		exit(0)


class Tree:

	def __init__(self, n, p):
		self.groups = [1]
		self.time = 0
		self.n = n
		p.sort()
		s = p[0]
		k = 0
		for t in p:
			if t == s:
				k += 1
			else:
				self.groups.append(k)
				s = t
				k = 1
		self.groups.append(k)
		self.groups.sort(reverse=True)
		self.k = len(self.groups)

	def afterksec(self):
		self.time += self.k
		for i in range(self.k):
			self.groups[i] -= self.k - i
		self.groups.sort(reverse=True)
		self.groups = list(filter(lambda x: x > 0, self.groups))

	def bin_cond(self, t):
		s = 0
		for b in self.groups:
			s += max(b - t, 0)
		return s <= t

	def bin_search(self):
		if self.groups == []:
			return 0
		l = 0
		r = self.n
		while l + 1 != r and l != r:
			m = (l + r) // 2
			if self.bin_cond(m):
				r = m
			else:
				l = m
		self.time += r
		self.groups = []

	def solve(self):
		self.afterksec()
		self.bin_search()
		return self.time
t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	tree = Tree(n, p)
	print(tree.solve())


for _ in range(int(input())):
	n = int(input())
	arr = [0 for i in range(n + 1)]
	arr[0] = 1
	for i in list(map(int, input().split())):
		arr[i] += 1
	arr.sort()
	arr = [i for i in arr if i != 0]
	n = len(arr)
	ans = n
	arr2 = [arr[i] - i - 1 for i in range(n) if arr[i] - i - 1 > 0]
	n = len(arr2)
	if n == 0:
		print(ans)
		continue
	arr3 = [0 for i in range(max(arr2))]
	n = len(arr3)
	for i in arr2:
		arr3[i - 1] += 1
	for i in range(n - 2, -1, -1):
		arr3[i] += arr3[i + 1]
	l = 0
	r = n - 1
	while l <= r:
		if arr3[l] <= 0:
			break
		ans += 1
		arr3[l] = 0
		if l == r:
			break
		arr3[r] -= 1
		if arr3[r] == 0:
			r -= 1
		l += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for j in l:
		d[j] = 0
	for j in l:
		d[j] += 1
	l1 = []
	for j in d:
		l1.append(d[j])
	l1.append(1)
	l1.sort()
	x = len(l1)
	t = 0
	for j in range(x):
		t += 1
		if l1[j] > j + 1:
			l1[j] -= j + 1
		else:
			l1[j] = 0
	c = sum(l1)
	l1.sort()
	ch = False
	for j in range(x):
		if l1[j] > 0:
			l1 = l1[j:]
			ch = True
			break
	if ch:
		l2 = [l1[0]]
		x = len(l1)
		for j in range(1, x):
			l2.append(l1[j] - l1[j - 1])
		x1 = 0
		while c - l2[x1] * (x - x1) >= l1[x1]:
			if x1 < x:
				c -= l2[x1] * (x - x1)
				x1 += 1
			else:
				break
		c -= l2[x1] * (x - x1)
		x2 = l1[x1] - c
		t += c
		r = x2 % (x - x1 + 1)
		d = x2 // (x - x1 + 1)
		t += (x - x1) * d + r
	print(t)


for _ in [0] * int(input()):
	n = int(input())
	a = list(map(int, input().split()))
	c = [0] * n + [1]
	for i in a:
		c[i - 1] += 1
	c = sorted(c, reverse=True)
	ans = sum((i > 0 for i in c))
	for (i, j) in enumerate(c):
		if j > 0:
			c[i] = i + j - ans
	c = sorted([i for i in c if i > 0], reverse=True)
	while c:
		ans += 1
		for (i, j) in enumerate(c):
			if j > 0:
				c[i] = j - 1 - (i == 0)
		c = sorted([i for i in c if i > 0], reverse=True)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	p = [int(i) for i in input().split()]
	children = [0] * n + [1]
	for i in p:
		children[i - 1] += 1
	children.sort(reverse=True)
	total_children = sum((i > 0 for i in children))
	for (i, j) in enumerate(children):
		if j > 0:
			children[i] = i + j - total_children
	children = sorted([i for i in children if i > 0], reverse=True)
	while children:
		total_children += 1
		for (i, j) in enumerate(children):
			if j > 0:
				children[i] = j - 1 - (i == 0)
		children = sorted([i for i in children if i > 0], reverse=True)
	print(total_children)


if True:
	from collections import Counter
	t = int(input())
	for _ in range(t):
		n = int(input())
		cnt = Counter({0: 1})
		cnt.update(map(int, input().split()))
		src = cnt.most_common()
		src.reverse()
		d = list(map(lambda x: max(x[1][1] - x[0] - 1, 0), enumerate(src)))
		d.sort(reverse=True)
		d.append(0)
		delta = max(d)
		res = delta
		i = 0
		while d and d[0] > 0:
			d[0] -= 1
			d = [dd - 1 for dd in d if dd > 0]
			d.sort(reverse=True)
			i += 1
		print(i + len(src))


from collections import Counter
from multiprocessing.connection import wait
testcases = input()

def can_do(waitlist, mid):
	extra_op = 0
	for i in waitlist:
		if mid < i:
			extra_op += i - mid
		mid -= 1
	return mid >= extra_op

def solve():
	n = int(input().strip())
	c = Counter(map(int, input().strip().split(' ')))
	c[0] = 1
	waitlist = sorted(c.values(), reverse=True)
	l = 0
	r = n
	while l < r:
		mid = (l + r) // 2
		if can_do(waitlist, mid):
			r = mid
		else:
			l = mid + 1
	return l
for caseNr in range(1, int(testcases) + 1):
	print('%s' % solve())


from collections import Counter, defaultdict, deque, namedtuple
from functools import lru_cache
from typing import List, Dict
import bisect as b
import heapq as h
import math as m

def inti():
	return int(input())

def ints():
	return [int(x) for x in input().split()]

def main_tc():
	n = inti()
	parents = ints()
	counter = defaultdict(int)
	counter[0] = 1
	for parent in parents:
		counter[parent] += 1
	numbers = []
	for (parent, count) in counter.items():
		numbers.append(count)
	numbers.sort(reverse=True)
	remaining = n
	answer = 0
	answer += len(numbers)
	for i in range(len(numbers)):
		infected = min(len(numbers) - i, numbers[i])
		numbers[i] -= infected
		remaining -= infected
	numbers.sort(reverse=True)
	while len(numbers) > 0 and numbers[-1] == 0:
		numbers.pop()
	second_answer = 0
	while len(numbers) > 0:
		second_answer += 1
		for i in range(len(numbers)):
			numbers[i] -= 1
			remaining -= 1
		if remaining <= second_answer:
			break
		while len(numbers) > 0 and numbers[-1] == 0:
			numbers.pop()
	print(answer + second_answer)

def main():
	tc = inti()
	for _ in range(tc):
		main_tc()
main()


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None

class doubly_linked_list:

	def __init__(self):
		self.head = None

	def push(self, NewVal):
		NewNode = Node(NewVal)
		NewNode.next = self.head
		if self.head is not None:
			self.head.prev = NewNode
		self.head = NewNode

	def remove(self, node):
		if node.prev:
			prev = node.prev
			next = node.next
			prev.next = node.next
			if next:
				next.prev = node.prev
		else:
			self.head = node.next
			if self.head:
				self.head.prev = None
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	amount_map = {}
	for i in a:
		amount_map[i] = amount_map.get(i, 0) + 1
	data = sorted(list(amount_map.values()) + [1], reverse=True)
	result = 0
	ijected = doubly_linked_list()
	circle = False
	result += len(data)
	n = len(data)
	for i in range(len(data)):
		data[i] -= n
		n -= 1
	data = [x for x in data if x > 0]
	while len(data):
		max_i = 0
		for i in range(len(data)):
			if data[i] > data[max_i]:
				max_i = i
		data[max_i] -= 1
		data = [x - 1 for x in data if x - 1 > 0]
		result += 1
	print(result)


t = int(input())
rr = ''
for _t in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = sorted(arr)
	new_arr = []
	nlist = []
	prev = None
	for a in arr:
		if a == prev or not nlist:
			nlist.append(a)
		else:
			new_arr.append(nlist)
			nlist = [a]
		prev = a
	if nlist:
		new_arr.append(nlist)
	arr = sorted(new_arr, key=lambda x: len(x), reverse=True)
	arr.append([0])

	def spread(l: list):
		nl = []
		for i in range(len(l)):
			if l[i] != 0:
				nl.append(l[i] - 1)
		if not nl:
			nl = [0]
		return nl
	inf_count = []
	seconds = 0
	for i in range(len(arr)):
		seconds += 1
		inf_count = spread(inf_count)
		inf_count.append(len(arr[i]) - 1)
	while True:
		inf_count = sorted(inf_count, reverse=True)
		if inf_count[0] == 0:
			break
		else:
			seconds += 1
			inf_count = spread(inf_count)
			if inf_count[0] != 0:
				inf_count[0] -= 1
	rr += str(seconds) + '\n'
print(rr)


from collections import defaultdict
import math
for _ in range(int(input())):
	n = int(input())
	l = [0] + list(map(int, input().split()))
	d = defaultdict(int)
	for i in range(n):
		d[l[i]] += 1
	ans = 0
	MAX = 0
	c = []
	for (i, v) in d.items():
		ans += 1
		MAX = max(MAX, v)
		c.append(v)
	c.sort(reverse=True)
	for i in range(len(c)):
		t = max(0, c[i] - len(c) + i)
		c[i] = t
	t = []
	for i in range(len(c)):
		if c[i] > 0:
			t.append(c[i])
	while t:
		t.sort(reverse=True)
		t[0] -= 1
		for i in range(len(t)):
			t[i] -= 1
		while t and t[-1] <= 0:
			t.pop()
		ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	branch = {}
	for i in a:
		branch[i] = branch.get(i, 0) + 1
	res = sorted(branch.values())[::-1]
	cnt = 0
	j = len(res)
	for i in range(len(res)):
		res[i] -= j
		j -= 1
		cnt += 1
	res = sorted(res)[::-1]
	while res[0] > 0:
		for i in range(len(res)):
			if i == 0:
				res[i] -= 2
				cnt += 1
			elif a[i] > 0:
				res[i] -= 1
		res = sorted(res)[::-1]
	print(cnt)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = Counter(a)
	floors = [[False, 1]]
	for (pr, ch) in cnt.items():
		floors.append([False, ch])
	floors.sort(key=lambda x: -x[1])
	secs = len(floors)
	jumps = secs
	for i in range(len(floors)):
		f = floors[i]
		f[0] = True
		f[1] -= jumps
		if f[1] < 0:
			f[1] = 0
		jumps -= 1
	while True:
		floors.sort(key=lambda x: -x[1])
		left = floors[0][1]
		if left == 0:
			break
		for i in range(len(floors)):
			f = floors[i]
			if f[0] and f[1] > 0:
				f[1] -= 1
		infect = False
		if not infect:
			for i in range(len(floors)):
				f = floors[i]
				if f[1] > 0:
					f[1] -= 1
					break
		secs += 1
	print(secs)


from heapq import heappop, heappush
t = int(input())
const = 1 << 18
for T in range(t):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	things = {0: const}
	for x in range(len(arr)):
		if arr[x] in things:
			things[arr[x]] += 1
		else:
			things[arr[x]] = const
	laze = []
	for x in things:
		heappush(laze, -things[x])
	time = 0
	while len(laze) > 0:
		f = -laze[0]
		if f <= time:
			heappop(laze)
			continue
		elif f >= const:
			f -= const
			f += time + 1
			heappop(laze)
			if f > time:
				heappush(laze, -f)
		else:
			f -= 1
			heappop(laze)
			if f > time:
				heappush(laze, -f)
		time += 1
	print(time)


import heapq
t = int(input())
while t:
	input()
	lst = [int(x) for x in input().split(' ')]
	n = len(lst) + 1
	g = []
	for _ in range(n + 1):
		g.append([])
	g[0].append(1)
	for i in range(len(lst)):
		g[lst[i]].append(i + 2)
	heap = []
	for (i, lst) in enumerate(g):
		if lst:
			heap.append((-len(lst), i))
	heapq.heapify(heap)
	(res, d) = (0, {})
	while heap or d:
		mx = float('-inf')
		nd = {}
		for p in d:
			d[p].pop()
			if len(d[p]) != 0:
				nd[p] = d[p]
				if mx < len(d[p]):
					(mx, infect) = (len(d[p]), p)
		d = nd
		if heap:
			p = heapq.heappop(heap)[1]
			g[p].pop()
			if g[p]:
				d[p] = g[p]
		elif d:
			d[infect].pop()
			if len(d[infect]) == 0:
				del d[infect]
		res += 1
	print(res)
	t -= 1


def calcula_t():
	n_vertices = int(input())
	grau = [0] * n_vertices
	lista_p = list(map(int, input().split()))
	for p in lista_p:
		grau[p - 1] += 1
	a = [1]
	for i in range(n_vertices):
		if grau[i] > 0:
			a.append(grau[i])
	a.sort(reverse=True)
	inicio = len(a)
	fim = n_vertices
	tempo = 0
	while inicio < fim:
		tempo = (inicio + fim) // 2
		soma = 0
		for i in range(len(a)):
			soma += max(0, a[i] - tempo + i)
		if soma + len(a) <= tempo:
			fim = tempo
		else:
			inicio = tempo + 1
	print(fim)
	pass
n_testes = int(input())
for i in range(n_testes):
	calcula_t()