The garden has a tree with too many leaves on it and gardner wants to cut the unwanted leaves. This is a rooted tree, where a node $v$ is called parent of another node $u$, if there exists a directed edge from $v$ to $u$. Leaf node is a node with no outgoing edges.
Gardner cuts the tree in a peculiar way:
- For each parent node(which has a valid leaf node attached to it), he cuts $x$ leaf nodes, such that $x$ is a multiple of 3.
Example : If a parent node has 7 leaf nodes, 6 leaf nodes will be cut and 1 will be left.
- If a parent has all its leaf nodes cut, only then the parent node itself becomes a new leaf node. If new leaf nodes are created, Gardner repeats step 1 until he can cut no more leaf nodes.
After completing all operations, gardner wants to know the minimum number of nodes left on the tree.

It is guaranteed that the given input is a rooted tree.
The root of the tree is vertex 1.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- First line of each testcase contains an integer $n$, the number of vertices in the tree. 
- Second line of each testcase contains array $A$ of size $n-1$, where $A_{i}(1≤i≤n-1)$, is the index of the parent of the $(i+1)^{th}$ vertex. 

-----Output:-----
For each testcase, output single integer, the number of nodes finally left on the tree.  

-----Constraints-----
- $1 \leq T \leq 10$
- $2 \leq n \leq 10^5$ 
- $1 \leq A_i \leq i$

-----Sample Input:-----
1

13

1 1 1 1 1 4 3 4 4 3 4 3 

-----Sample Output:-----
4

-----EXPLANATION:-----

Difficulty: interview

Starter code:

Solutions:
def dfs(node):
 nonlocal adj,leaf
 val=0
 flag=0
 for i in adj[node]:
  x= dfs(i)
  val+=x
  if x==0:
   flag=1
 leaf+=val-val%3
 if val%3==0 and flag==0:
  return 1
 else:
  return 0
for _ in range(int(input())):
 n=int(input())
 adj=[[] for i in range(n+2)]
 arr=[int(i) for i in input().split()]
 leaf=0
 #print(adj)
 for i in range(2,n+1):
  #print(i,arr[i-2])
  adj[arr[i-2]].append(i)
  
 dfs(1)
 print(n-leaf)

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




def dfs(node):
 visited[node]=True
 n0[node]+=1
 for x in d[node]:
  if visited[x]==False:
   dfs(x)
   n0[node]+=n0[x]
def dfs1(node):
 nonlocal ans
 visited[node]=True
 co=0
 for x in d[node]:
  if visited[x]==False:

   dfs1(x)
   if n0[x]==1:
    co+=1

 ans1=co//3
 ##print(ans1,node)
 if 3*ans1==len(d[node]):
  n0[node]=1
  ##print(n0[node],node)
 ans-=3*ans1





for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 d=defaultdict(list)
 ans=n
 for i in range(len(a)):
  d[a[i]].append(i+2)
 ##print(d)
 visited = [False] * (n + 1)
 n0 = [0] * (n + 1)
 ##print(n0)
 dfs(1)
 ## print(n0)
 visited=[False]*(n+1)
 dfs1(1)
 print(ans)