The MEX of a set of integers is defined as the smallest non-negative integer that does not belong to this set. For example, $\mathrm{MEX}(\{0,2,3\}) = 1$ and $\mathrm{MEX}(\{1,3\}) = 0$.
Chef has a tree with $N$ nodes (numbered $1$ through $N$). The tree is rooted at node $1$. Chef wants to assign a non-negative integer to each node in such a way that each integer between $0$ and $N-1$ (inclusive) is assigned to exactly one node.
For each node $u$, consider the integers assigned to the nodes in the subtree of $u$ (including $u$); let $a_u$ denote the MEX of these integers. Chef wants $a_1 + a_2 + \ldots + a_N$ to be as large as possible. Find the maximum possible value of this sum.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N-1$ space-separated integers $p_1, p_2, \ldots, p_{N-1}$. For each valid $i$, the node $p_i$ is the parent of the node $i+1$.

-----Output-----
For each test case, print a single line containing one integer ― the maximum sum of subtree MEX-s which can be obtained if you assign the weights optimally.

-----Constraints-----
- $1 \le T \le 5$
- $2 \le N \le 10^5$
- $1 \le p_i < i$ for each valid $i$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
2
3
1 1
5
1 1 2 2

-----Example Output-----
4
9

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Greedy algorithms

Tree algorithms

Data structures
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
import sys
(input, print) = (sys.stdin.readline, sys.stdout.write)
sys.setrecursionlimit(10 ** 6)

def ans(dic, n):
	if dic.get(n) != None:
		b = []
		for a in dic[n]:
			b.append(ans(dic, a))
		mx = 0
		node = 0
		for a in b:
			if a[0] > mx:
				mx = a[0]
			node += a[1]
		node += len(dic[n])
		return (mx + node + 1, node)
	else:
		return (1, 0)
for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	dic = {}
	for j in range(1, n):
		temp = a[j - 1]
		if dic.get(temp) == None:
			dic[temp] = [j + 1]
		else:
			dic[temp].append(j + 1)
	anss = ans(dic, 1)
	print(str(anss[0]) + '\n')


import sys
sys.setrecursionlimit(10 ** 6)

def recurse(root):
	if adj[root] == []:
		return (1, 1)
	sub = 1
	max1 = 0
	for v in adj[root]:
		(x, y) = recurse(v)
		sub += x
		max1 = max(max1, y)
	return (sub, sub + max1)
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	adj = {}
	for i in range(1, n + 1):
		adj[i] = []
	for i in range(n - 1):
		(parent, child) = (p[i], i + 2)
		adj[parent].append(child)
	(x, y) = recurse(1)
	print(y)


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

def max_mex(dept):
	for i in at_dept[dept]:
		(m, l) = (0, 0)
		for j in child[i]:
			m = max(m, mex[j][1])
			l += mex[j][0]
		mex[i] = [l + 1, m + l + 1]
	if dept > 1:
		max_mex(dept - 1)

def all_dept(arr, dept=2):
	for i in arr:
		at_dept[dept].append(i)
		all_dept(child[i], dept + 1)
for T in range(int(input())):
	n = int(input())
	parent = list(map(int, input().split()))
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		child[parent[i]].append(i + 2)
	at_dept = [[] for i in range(n + 1)]
	at_dept[1].append(1)
	all_dept(child[1])
	for arr in at_dept[::-1]:
		if arr == []:
			at_dept.pop()
		else:
			break
	mex = [0] * (n + 1)
	for i in at_dept[-1]:
		mex[i] = [1, 1]
	max_mex(len(at_dept) - 2)
	print(mex[1][1])


import sys
sys.setrecursionlimit(10 ** 6)
input = __import__('sys').stdin.readline

def number_of_elements(dec, mem, node):
	if node in mem:
		return mem[node]
	res = 1
	for j in dec[node]:
		res += number_of_elements(dec, mem, j)
	mem[node] = res
	return res

def solve(dec, mem2, node, mem):
	if node in mem2:
		return mem2[node]
	if not dec[node]:
		mem2[node] = 1
		return 1
	ans = mem[node]
	p = 1
	for j in dec[node]:
		p = max(p, solve(dec, mem2, j, mem))
	mem2[node] = ans + p
	return ans + p
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dec = {}
	for i in range(n - 1):
		if a[i] in dec:
			dec[a[i]].append(i + 2)
		else:
			dec[a[i]] = [i + 2]
	for i in range(1, n + 1):
		if i not in dec:
			dec[i] = []
	mem = {}
	number_of_elements(dec, mem, 1)
	result = solve(dec, {}, 1, mem)
	print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {i + 1: [] for i in range(n)}
	for i in range(n - 1):
		d[l[i]] += [i + 2]
	ch = {i + 1: 0 for i in range(n)}
	levels = []
	queue = [1]
	while len(queue) != 0:
		levels.append(queue.copy())
		nq = len(queue.copy())
		for i in range(nq):
			for j in d[queue[i]]:
				queue.append(j)
		queue = queue[nq:]
	for i in range(len(levels) - 1, 0, -1):
		for node in levels[i]:
			ch[l[node - 2]] += ch[node] + 1
	ans = 0
	lst = list(ch.values())
	for i in range(n):
		lst[i] += 1
	for lev in levels[1:]:
		for i in lev:
			parent = l[i - 2]
			lst[i - 1] += lst[parent - 1]
	ans = max(lst)
	print(ans)


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

def dfs(p):
	(val, nm) = (0, 1)
	for i in child[p]:
		(x, mex) = dfs(i)
		nm += mex
		val = max(val, x)
	return [val + nm, nm]
for T in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		child[p[i]].append(i + 2)
	print(dfs(1)[0])


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

def dfsnr(node, tree):
	stack = [node]
	visited = set()
	result = dict()
	while stack.__len__() != 0:
		item = stack[-1]
		if item not in visited:
			visited.add(item)
			if item in tree.keys():
				stack += tree[item]
		else:
			m = -1
			count = 1
			if item in tree.keys():
				for i in tree[item]:
					if m < result[i][0]:
						m = result[i][0]
					count += result[i][1]
			else:
				m = 0
			result[item] = (m + count, count)
			stack.pop()
	print(result[1][0])

def test_case():
	N = int(input())
	L = input_int_list()
	tree = dict()
	for i in range(len(L)):
		if L[i] in tree.keys():
			tree[L[i]].append(i + 2)
		else:
			tree[L[i]] = [i + 2]
	dfsnr(1, tree)
T = int(input())
for t in range(T):
	test_case()


from sys import setrecursionlimit
setrecursionlimit(999999)

def children(g, n, child):
	if n in g.keys():
		x = 0
		for adg in g[n]:
			x += children(g, adg, child)
		child[n] = len(g[n]) + x
		return len(g[n]) + x
	else:
		child[n] = 0
		return 0

def check(g, n, child):
	if n in g.keys():
		x = 0
		for adg in g[n]:
			l = check(g, adg, child)
			if l > x:
				x = l
		if x > 0:
			return child[n] + 1 + x
	else:
		return 1
for _ in range(int(input())):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	tree = {}
	for i in range(1, n):
		tree[a[i]] = tree.setdefault(a[i], [])
		tree[a[i]].append(i + 1)
	child = [0] * (n + 1)
	children(tree, 1, child)
	print(check(tree, 1, child))


import sys
sys.setrecursionlimit(10 ** 7)
import math
from collections import Counter
adj = [[] for i in range(100005)]

def dfs(node):
	mex = 0
	size = 1
	for i in adj[node]:
		temp = dfs(i)
		mex = max(mex, temp[0])
		size += temp[1]
	return [mex + size, size]
try:
	for _ in range(int(input())):
		n = int(input())
		for i in range(1, n + 1):
			adj[i].clear()
		arr = [int(i) for i in input().split()]
		for i in range(1, n):
			adj[arr[i - 1]].append(i + 1)
		ans = dfs(1)
		print(ans[0])
except EOFError as e:
	print(e)


for _ in range(int(input())):
	n = int(input())
	con = list(map(int, input().split()))
	le = [1 for i in range(n)]
	for i in range(n - 2, -1, -1):
		le[con[i] - 1] += le[i + 1]
	ans = [0 for i in range(n)]
	ma = 0
	tra = [[] for i in range(n + 1)]
	no = 2
	for i in con:
		tra[i].append(no)
		no += 1
	bfs = [1]
	l = 0
	while l < len(bfs):
		go = bfs[l]
		for i in tra[go]:
			bfs.append(i)
		l += 1
	ans[0] = le[0]
	for i in range(1, n, 1):
		ci = bfs[i]
		va = le[ci - 1] + ans[con[ci - 2] - 1]
		if va > ma:
			ma = va
		ans[ci - 1] = va
	print(ma)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
	else:
		l = list(map(int, input().split()))
		mex = 0
		d = defaultdict(lambda : [])
		for (i, num) in enumerate(l):
			d[num - 1].append(i + 1)

		def dfs(i):
			mex = 0
			size = 1
			for j in d[i]:
				if i == j:
					continue
				x = dfs(j)
				mex = max(mex, x[0])
				size += x[1]
			return [mex + size, size]
		print(dfs(0)[0])


import sys
sys.setrecursionlimit(int(1000000.0))

def solve(graph, cur):
	if not graph[cur]:
		return (1, 1)
	tot = 0
	ans = 0
	for child in graph[cur]:
		(prevans, tnodes) = solve(graph, child)
		tot += tnodes
		ans = max(ans, prevans)
	return (tot + 1 + ans, tot + 1)
for t in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	from collections import defaultdict
	graph = defaultdict(list)
	for i in range(n - 1):
		graph[lis[i]].append(i + 2)
	print(solve(graph, 1)[0])


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class Graph:

	def __init__(self, V):
		self.graph = [[] for i in range(V + 1)]
		self.Visited = set()
		self.height = 1

	def addEdges(self):
		arr = [int(x) for x in input().split()]
		for i in range(len(arr)):
			self.graph[i + 1].append(arr[i] - 1)
			self.graph[arr[i] - 1].append(i + 1)

	def DFS(self, Node):
		self.Visited.add(Node)
		if len(self.graph[Node]) == 0:
			return (1, 1)
		node = 1
		mex = 1
		for each in self.graph[Node]:
			if each not in self.Visited:
				(n1, m1) = self.DFS(each)
				node += n1
				mex = max(m1, mex)
		return (node, mex + node)
for _ in range(int(input())):
	V = int(input())
	gra = Graph(V)
	gra.addEdges()
	(x, y) = gra.DFS(0)
	print(y - 1)


from sys import stdin, setrecursionlimit as srl
from threading import stack_size, Thread
srl(int(1000000000.0) + 7)
stack_size(int(100000000.0))

def dfs_size(d, root):
	s = 1
	for i in d[root]:
		if vis[i] == 0:
			vis[i] = 1
			s += dfs_size(d, i)
	size[root] = s
	return s

def mex(n):
	x = size[n]
	if len(d[n]) == 0:
		return 1
	p = -1
	for i in d[n]:
		p = max(p, mex(i))
	return x + p
t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[i] = []
	for i in range(1, n):
		d[p[i - 1] - 1].append(i)
	vis = [0 for i in range(n)]
	size = [0 for i in range(n)]
	vis[0] = 1
	size[0] = dfs_size(d, 0)
	print(mex(0))


from sys import setrecursionlimit
setrecursionlimit(999999)
from collections import defaultdict as dd
from collections import deque as dq

def dfs_rec(g, root):
	if len(g[1]) == 0:
		return [1, 1]
	(sz, mx) = (1, -1)
	for i in range(len(g[root])):
		temp = dfs_rec(g, g[root][i])
		sz += temp[0]
		mx = max(mx, temp[1])
	return [sz, mx + sz]
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = dd(list)
	for i in range(n - 1):
		g[l[i]].append(i + 2)
	r = dfs_rec(g, 1)[1]
	print(r + 1)


import sys

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
sys.setrecursionlimit(10 ** 6)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def string(s):
	return ''.join(s)

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def bo(i):
	return ord(i) - ord('A')

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
while t > 0:
	t -= 1
	n = fi()
	p = li()
	a = [[] for i in range(n + 1)]
	for i in range(n - 1):
		a[i + 2].append(p[i])
		a[p[i]].append(i + 2)
	subtree = [1] * (n + 1)

	def dfs(i, par=-1):
		for j in a[i]:
			if j != par:
				dfs(j, i)
				subtree[i] += subtree[j]
	dfs(1, -1)
	ans = [0] * (n + 1)
	for i in range(1, n + 1):
		if i == 1:
			ans[i] = n
		else:
			ans[i] += subtree[i] + ans[p[i - 2]]
	print(max(ans))


import sys
sys.setrecursionlimit(10 ** 6)

def recurse(root):
	if root not in dic:
		return (1, 1)
	sum1 = 1
	max1 = 0
	for i in dic[root]:
		(x, y) = recurse(i)
		sum1 += x
		max1 = max(max1, y)
	return (sum1, sum1 + max1)
for _ in range(int(input())):
	n = int(input())
	dic = {}
	lis = list(map(int, input().split()))
	for i in range(len(lis)):
		if lis[i] not in dic:
			dic[lis[i]] = [i + 2]
		else:
			dic[lis[i]].append(i + 2)
	(x, y) = recurse(1)
	print(y)


from collections import deque, defaultdict
for _ in range(int(input())):
	n = int(input())
	p = [int(i) for i in input().split()]
	graph = [[] for i in range(n)]
	for i in range(len(p)):
		graph[p[i] - 1].append(i + 1)
	count = n
	vis = [0] * n
	q = deque()
	q.append(0)
	vis[0] = 1
	dist = [0] * n
	temp = 2
	while len(q) != 0:
		curr = q.popleft()
		for i in graph[curr]:
			if vis[i] == 0:
				dist[i] = dist[curr] + 1
				vis[i] = 1
				q.append(i)
	d = []
	for i in range(n):
		d.append([dist[i], i])
	d.sort(reverse=True)
	value = defaultdict(lambda : 1)
	for i in range(n - 1):
		value[p[d[i][1] - 1] - 1] += value[d[i][1]]
	vis = [0] * n
	q = deque()
	q.append(0)
	vis[0] = 1
	dist = [0] * n
	temp = 2
	while len(q) != 0:
		curr = q.popleft()
		for i in graph[curr]:
			if vis[i] == 0:
				value[i] += value[curr]
				vis[i] = 1
				q.append(i)
	ans = 0
	for i in value:
		ans = max(ans, value[i])
	print(ans)


import sys
sys.setrecursionlimit(1000000)

def dfs(root, graph):
	retrieval = []
	try:
		for i in graph[root]:
			retrieval.append(dfs(i, graph))
		if retrieval != []:
			mx = retrieval[0][0] + retrieval[0][1]
			totalNodesInSubtree = 0
			for i in retrieval:
				totalNodesInSubtree += i[1]
				if i[0] + i[1] > mx:
					mx = i[0] + i[1]
			return [mx, totalNodesInSubtree + 1]
		else:
			return [0, 1]
	except:
		return [0, 1]
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	graph = {}
	for i in range(n - 1):
		if graph.get(l[i]):
			graph[l[i]].add(i + 2)
		else:
			graph[l[i]] = set([i + 2])
	ans = dfs(1, graph)
	print(ans[0] + ans[1])


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
t = int(input())

def dfs(n, p, a):
	count = 0
	maxval = 0
	for i in a[n]:
		if i == p:
			continue
		(tmaxval, tcount) = dfs(i, n, a)
		maxval = max(maxval, tmaxval)
		count += tcount
	return (maxval + count + 1, count + 1)
for _ in range(t):
	n = int(input())
	a = []
	for i in range(n + 1):
		a.append(list())
	e = list(map(int, input().split()))
	for i in range(1, n):
		a[e[i - 1]].append(i + 1)
	print(dfs(1, 1, a)[0])


from math import log2
import sys
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
inf = float('inf')

def find_height(node):
	nodes[node] = 1
	for i in graph[node]:
		nodes[node] += find_height(i)
	return nodes[node]

def find_sum(node):
	suma = nodes[node]
	maxa = 0
	for i in graph[node]:
		maxa = max(find_sum(i), maxa)
	return maxa + suma
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	graph = defaultdict(set)
	for i in range(len(l)):
		graph[l[i]].add(i + 2)
	nodes = defaultdict(int)
	find_height(1)
	ans = find_sum(1)
	print(ans)


import sys, math
from collections import defaultdict as dd
sys.setrecursionlimit(10 ** 6)
input = lambda : sys.stdin.readline().strip()
inp = lambda : list(map(int, input().split()))

def lcm(a, b):
	return a * b // math.gcd(a, b)
for _ in range(int(input())):
	(n,) = inp()
	a = list(map(int, input().split()))
	g = dd(lambda : [])
	for i in range(2, n + 1):
		g[a[i - 2]].append(i)
	nodes = [0 for i in range(n + 1)]

	def dfs(node=1):
		res = 1
		for to in g[node]:
			res += dfs(to)
		nodes[node] = res
		return res
	dfs()

	def dfs1(node=1):
		res = [0]
		for to in g[node]:
			res.append(dfs1(to))
		return max(res) + nodes[node]
	print(dfs1())


from sys import setrecursionlimit
setrecursionlimit(999999)

def createTree(n, par):
	graph = [[] for i in range(n + 1)]
	for i in range(len(par)):
		graph[par[i]].append(i + 2)
	return graph

def recurse(graph, root):
	if len(graph[root]) == 0:
		return [1, 1]
	noNodes = 1
	root_sum = -1
	for i in range(len(graph[root])):
		temp = recurse(graph, graph[root][i])
		noNodes += temp[0]
		root_sum = max(root_sum, temp[1])
	return [noNodes, root_sum + noNodes]
for i in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	graph = createTree(n, arr)
	print(recurse(graph, 1)[1])


from sys import setrecursionlimit
setrecursionlimit(110000)

class Node:

	def __init__(self):
		self.children = []
		self.subtree_children_count = 0

def post_order(node):
	count = 1
	for child in node.children:
		child_sub_trees = post_order(child)
		count += child_sub_trees
	node.subtree_children_count = count
	return node.subtree_children_count

def subtree_count(root):
	try:
		return post_order(root)
	except ArithmeticError:
		return -1

def assign_parents(parents, nodes):
	for (i, parent) in enumerate(parents, 1):
		nodes[parent].children.append(nodes[i + 1])

def get_submex(root):
	ans = -1

	def maximizer(node, prev=0):
		nonlocal ans
		value = node.subtree_children_count + prev
		ans = max(ans, value)
		for child in node.children:
			maximizer(child, value)
	maximizer(root)
	return ans

def solve():
	for _ in range(int(input())):
		n = int(input())
		parents = list(map(int, input().strip().split()))
		nodes = [Node() for _ in range(n + 1)]
		assign_parents(parents, nodes)
		root = nodes[1]
		if subtree_count(root) == -1:
			print(42)
			continue
		result = get_submex(root)
		print(result)
solve()


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().strip().split()))
	ans = [0] * (n + 1)
	nos = [1] * (n + 1)
	for i in range(n - 2, -1, -1):
		nos[p[i]] += nos[i + 2]
		ans[i + 2] += nos[i + 2]
		ans[p[i]] = max(ans[p[i]], ans[i + 2])
	print(ans[1] + nos[1])


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

def traverse(node):
	visited[node] = 1
	for ad in graph[node]:
		if visited[ad] == 0:
			traverse(ad)
	m = 0
	for ad in graph[node]:
		node_count[node] += node_count[ad]
		m = max(m, dp[ad])
	dp[node] += m + node_count[node]
for _ in range(int(input())):
	n = int(input())
	p = [0] + [int(x) for x in input().split()]
	graph = defaultdict(list)
	for i in range(1, n):
		graph[p[i]].append(i + 1)
	dp = [0] * (n + 1)
	node_count = [1] * (n + 1)
	visited = defaultdict(int)
	traverse(1)
	print(dp[1])


import sys
sys.setrecursionlimit(1000000)

def dfs(root, parent, op):
	val = 0
	if root in dic:
		for child in dic[root]:
			if child != parent:
				val += dfs(child, root, op)
	op[root] = val + 1
	return op[root]

def dfs2(root, parent, op):
	val = -1
	if root in dic:
		for child in dic[root]:
			if child != parent:
				val = max(val, dfs2(child, root, op), 0)
	if val == -1:
		return 1
	else:
		return op[root] + val
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dic = {}
	for i in range(n - 1):
		x = arr[i]
		if x in dic:
			dic[x].append(i + 2)
		else:
			dic[x] = [i + 2]
		if i + 2 in dic:
			dic[i + 2].append(x)
		else:
			dic[i + 2] = [x]
	op = [0 for i in range(n + 1)]
	parent = 0
	root = 1
	dfs(root, parent, op)
	print(dfs2(root, parent, op))


from sys import stdin
import sys
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict as dd

def dfs(tree, cur):
	if cur not in tree:
		lensub[cur] = 0
		return 0
	else:
		for i in tree[cur]:
			lensub[cur] += dfs(tree, i) + 1
		return lensub[cur]

def fun(tree, cur):
	if lensub[cur] == 0:
		return 1
	mx = None
	for i in tree[cur]:
		var = fun(tree, i) + lensub[cur] + 1
		if mx == None or var > mx:
			mx = var
	return mx
I = stdin.readline
for _ in range(int(I())):
	n = int(I())
	ar = list(map(int, I().split()))
	tree = dd(list)
	for i in range(n - 1):
		tree[ar[i]].append(i + 2)
	global lensub
	lensub = dd(int)
	dfs(tree, 1)
	ans = fun(tree, 1)
	print(ans)


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)

def dfs(node, visited):
	visited[node] = 1
	p = 1
	q = 0
	for v in g[node]:
		if visited[v] == 0:
			m = dfs(v, visited)
			p = p + m
	no[node] = p
	return p

def dfs2(node, visited, no):
	visited[node] = 1
	p = 0
	for v in g[node]:
		if visited[v] == 0:
			p = max(p, dfs2(v, visited, no))
	no[node] += p
	return no[node]
t = int(input())
an = 0
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = 0
	g = defaultdict(list)
	no = [0] * (n + 1)
	for j in range(n - 1):
		g[a[j]].append(j + 2)
		g[j + 2].append(a[j])
	visited = [0] * (n + 1)
	dfs(1, visited)
	visited = [0] * (n + 1)
	m = dfs2(1, visited, no)
	print(m)


import sys
sys.setrecursionlimit(10 ** 6)
for _ in range(int(input())):
	n = int(input())
	from collections import defaultdict
	g = defaultdict(list)
	ls = list(map(int, input().split()))
	for i in range(2, n + 1):
		g[ls[i - 2]].append(i)
	sz = [1] * (n + 1)
	dp = [0] * (n + 1)
	ans = [0] * (n + 1)

	def dfs(s):
		for i in g[s]:
			dfs(i)
			sz[s] += sz[i]
			dp[s] = max(dp[s], dp[i] + 1)
		for i in g[s]:
			ans[s] = max(ans[i], ans[s])
		ans[s] += sz[s]
	dfs(1)
	for i in range(1, n + 1):
		g[i].sort(key=lambda k: [-dp[k], -sz[k]])
	mp = {}
	s = 1
	res = 1
	while g[s]:
		res += sz[s]
		s = g[s][0]
	print(ans[1])


from sys import stdin as stin, stdout as stout, setrecursionlimit as srl
from collections import defaultdict as dd, Counter, deque as dq
srl(10 ** 6)

def get_ints():
	return map(int, stin.readline().split())

def get_list():
	return list(map(int, stin.readline().split()))

def get_int():
	return int(stin.readline())

def get_str():
	return stin.readline()

def dfs(graph, u, parent):
	(size, max_mex) = (0, 0)
	for i in graph[u]:
		if i == parent:
			continue
		(tmax, tsize) = dfs(graph, i, u)
		max_mex = max(max_mex, tmax)
		size += tsize
	return (max_mex + size + 1, size + 1)
for _ in range(get_int()):
	n = get_int()
	nums = get_list()
	graph = dd(list)
	for i in range(2, n + 1):
		graph[nums[i - 2]].append(i)
	print(dfs(graph, 1, 1)[0])