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: interview

Starter code:

Solutions:
# cook your dish here
# cook your dish here
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)





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])

#================= author:------sushmanth ========================

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])


    
    


# cook your dish here
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={}
    for i in at_dept[-1]:
        mex[i]=[1,1]

    max_mex(len(at_dept)-2)

    print(mex[1][1])


    
    


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 = 0
    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])


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))	

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(g)
    print(r+1)

# cook your dish here
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)
    

# cook your dish here
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])


import sys
sys.setrecursionlimit(int(1e6))
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])

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])

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()
    #print(gra.graph)
    x,y=gra.DFS(0)
    print(y-1)
    #print(height*height)
    #print((gra.height*(gra.height+1))//2)


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")

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)
#from sys import stdin,stdout
import math
#import random
#import heapq
from collections import Counter
#from queue import PriorityQueue
#from functools import lru_cache
#@lru_cache(maxsize=None) #for optimizing the execution time of callable objects/functions(placed above callable functions)
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):
            #print(arr[i-1])
            adj[arr[i-1]].append(i+1)
            #adj[i].append(arr[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)








# cook your dish here
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 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])


from sys import stdin as stin,stdout as stout,setrecursionlimit as srl
from collections import defaultdict as dd,Counter,deque as dq 
#from heapq import heapify,heappush as hpu,heappop as hpo
#import math 
#import numpy
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])