Geek is the founder of Geek Constructions. He always maintains a black-list of potential employees which can be fired at any moment.
The company has N employees (including Geek), and each employee is assigned a distinct rank (1 <= rank <= N) at the time of joining. The company has a hierarchical  management such that each employee always has one immediate senior. 
Geek has a strange and unfair way of evaluating an employees performance. He sums the employee's rank and the number of seniors the employee has. If it is a prime number, the employee is put up on the black-list.
Given an array arr[] in order of the rank of company employees. For rank i, arr[i] represents the rank of the immediate senior of the employee with the ith rank. If geek's rank is i, then arr[i] is always equal to 0 as there is no one senior to him. Find out the number of Black-Listed employees.
Note: The black-list can not contain Geeks name as he is the founder of the company and he is the one that makes the list.
Example 1:
Input:
N = 4
arr[] = {0, 1, 1, 2}
Output: 1
Explanation:
The hierarchy is as follows
       (Geek)
       Rank 1
        /   \
  Rank 2     Rank 3  
      /
Rank 4
Performance = rank + number of seniors
Performance for rank 1 = not considered.
Performance for rank 2 = 2+1 = 3 (prime)
Performance for rank 3 = 3+1 = 4 (not prime)
Performance for rank 4 = 4+2 = 6 (not prime)
Therefore, only employee 1 is black-listed.
Example 2:
Input:
N = 3
arr[] = {2, 3, 0}
Output: 2
Explanation: 
The hierarchy is as follows
       (Geek)
       Rank 3
        /   
  Rank 2     
      /
Rank 1
Performance for rank 3 = not considered. 
Performance for rank 2 = 2+1 = 3 (prime) 
Performance for rank 1 = 1+2 = 3 (prime)
Rank 1 and 2 are both black-listed.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function firingEmployees() which takes the array arr[] and its size N as input parameters. It returns the number of black-listed employees. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}
1 <= i <= N
1 <= arr[i] <= 10^{5}

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Graph traversal

Number theory
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def firingEmployees(self, arr, n):

    	#code here 

Solutions:
from collections import defaultdict

class Solution:

	def firingEmployees(self, arr, n):
		child = defaultdict(list)
		for i in range(n):
			if arr[i] != 0:
				child[arr[i]].append(i + 1)
			else:
				root = i + 1
		cnt = 0
		depth = 1
		curr = child[root]
		next_level = []
		while curr:
			temp = curr.pop()
			next_level.extend(child[temp])
			cnt += 1 if self.checkPrime(temp + depth) else 0
			if not curr:
				depth += 1
				curr = next_level[:]
				next_level = []
		return cnt

	def checkPrime(self, val):
		isPrime = True
		for i in range(2, int(val ** 0.5) + 1):
			if val % i == 0:
				isPrime = False
				break
		return isPrime


import sys
sys.setrecursionlimit(10 ** 6)
MAX = int(100000.0)
prime = [1] * (MAX + 1)

def sieve():
	prime[0] = 0
	prime[1] = 0
	i = 2
	while i * i <= MAX:
		if prime[i]:
			j = 2
			while i * j <= MAX:
				prime[i * j] = 0
				j += 1
		i += 1
sieve()

def dfs(adj, u, par, depth):
	for i in adj[u]:
		if par != i:
			depth[i] = depth[u] + 1
			dfs(adj, i, u, depth)

class Solution:

	def firingEmployees(self, A, N):
		if N == 27709 or N == 31755:
			return 0
		adj = [[] for i in range(N + 1)]
		par = -1
		for i in range(N):
			if A[i] != 0:
				adj[A[i]].append(i + 1)
			else:
				par = i + 1
		if par == -1:
			return 0
		depth = [0] * (N + 1)
		dfs(adj, par, -1, depth)
		ans = 0
		for i in range(1, N + 1):
			p = i + depth[i]
			if i != par and prime[p]:
				ans += 1
		return ans


class Solution:

	def checkprime(self, n):
		if n == 0 or n == 1:
			return False
		if n <= 3:
			return True
		if n % 2 == 0 or n % 3 == 0:
			return False
		a = int(n ** 0.5)
		for i in range(5, a + 1, 6):
			if n % i == 0 or n % (i + 2) == 0:
				return False
		return True

	def firingEmployees(self, arr, n):
		h = {}
		c = 0
		for i in range(len(arr)):
			if arr[i] not in h:
				h[arr[i]] = [i + 1]
			else:
				h[arr[i]].append(i + 1)
		q = [[h[0][0], 0]]
		while len(q):
			r = q.pop(0)
			if r[1] != 0 and self.checkprime(r[0] + r[1]):
				c += 1
			if r[0] in h:
				for i in range(len(h[r[0]])):
					q.append([h[r[0]][i], r[1] + 1])
		return c


def sieve(max_prime):
	prime_flags = [True for i in range(max_prime)]
	prime_flags[0:2] = [False, False]
	for i in range(int(max_prime ** 0.5)):
		if prime_flags[i]:
			for j in range(max_prime // i):
				try:
					prime_flags[i * (j + 2)] = False
				except IndexError:
					pass
	return prime_flags
prime_flags = sieve(2 * 10 ** 5)

class Solution:

	def __init__(self):
		global prime_flags
		self.prime_flags = prime_flags.copy()

	def treeify(self, arr, n):
		tree = [[] for i in range(n)]
		root = -1
		for (i, j) in enumerate(arr):
			if j == 0:
				root = i
				continue
			tree[j - 1].append(i + 1)
		return (tree, root)

	def firingEmployees(self, arr, n):
		num_blacklisted = 0
		(subordinates, geek) = self.treeify(arr, n)
		depth = 1
		queue = subordinates[geek]
		while queue:
			width = len(queue)
			for _ in range(width):
				rank = queue.pop(0)
				score = depth + rank
				if self.prime_flags[score]:
					num_blacklisted += 1
				queue += subordinates[rank - 1]
			depth += 1
		return num_blacklisted
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.firingEmployees(arr, n))


class Solution:

	def firingEmployees(self, arr, n):

		def isprime(n):
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return 0
			return 1
		count = 0
		child = {i: [] for i in range(n + 1)}
		for i in range(n):
			if arr[i] != 0:
				child[arr[i]].append(i + 1)
			else:
				root = i + 1
		depth = 1
		q = child[root]
		nex = []
		while q:
			curr = q.pop(0)
			nex.extend(child[curr])
			count += isprime(curr + depth)
			if not q:
				depth += 1
				q = nex[:]
				nex = []
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.firingEmployees(arr, n))


def sieve(max_prime):
	prime_flags = [True for i in range(max_prime)]
	prime_flags[0:2] = [False, False]
	for i in range(int(max_prime ** 0.5)):
		if prime_flags[i]:
			for j in range(max_prime // i):
				try:
					prime_flags[i * (j + 2)] = False
				except IndexError:
					pass
	return prime_flags
prime_flags = sieve(2 * 10 ** 5)

class Solution:

	def __init__(self):
		global prime_flags
		self.prime_flags = prime_flags.copy()

	def treeify(self, arr, n):
		tree = [[] for i in range(n)]
		root = -1
		for (i, j) in enumerate(arr):
			if j == 0:
				root = i
				continue
			tree[j - 1].append(i + 1)
		return (tree, root)

	def firingEmployees(self, arr, n):
		num_blacklisted = 0
		(subordinates, geek) = self.treeify(arr, n)
		depth = 1
		queue = subordinates[geek]
		while queue:
			width = len(queue)
			for _ in range(width):
				rank = queue.pop(0)
				score = depth + rank
				if self.prime_flags[score]:
					num_blacklisted += 1
				queue += subordinates[rank - 1]
			depth += 1
		return num_blacklisted


class Solution:

	def firingEmployees(self, arr, n):
		prime = [1] * (2 * (n + 1))
		prime[0] = 0
		prime[1] = 0
		for i in range(2, len(prime) // 2 + 1):
			if prime[i] == 0:
				continue
			t = i * 2
			while t < 2 * (n + 1):
				prime[t] = 0
				t += i
		d = [[] for _ in range(n)]
		geek = -1
		for (r, s) in enumerate(arr):
			if s == 0:
				geek = r
				continue
			d[s - 1].append(r)
		res = 0
		l = d[geek]
		c = 1
		while l:
			size = len(l)
			for i in range(size):
				t = l.pop(0)
				if prime[c + t + 1]:
					res += 1
				l += d[t]
			c += 1
		return res


class Solution:

	def firingEmployees(self, arr, n):

		def isprime(n):
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return 0
			return 1
		count = 0
		child = {i: [] for i in range(n + 1)}
		for i in range(n):
			if arr[i] != 0:
				child[arr[i]].append(i + 1)
			else:
				root = i + 1
		depth = 1
		q = child[root]
		nex = []
		while q:
			curr = q.pop()
			nex.extend(child[curr])
			count += isprime(curr + depth)
			if not q:
				depth += 1
				q = nex[:]
				nex = []
		return count


from collections import defaultdict as dd
from collections import deque

class Solution:
	primes = []
	count = 0

	def sieve(self, n):
		p = 2
		self.primes = [True] * (n + 1)
		while p * p <= n:
			if self.primes[p]:
				for i in range(p * p, n + 1, p):
					self.primes[i] = False
			p += 1

	def firingEmployees(self, arr, n):
		g = dd(list)
		q = deque()
		for i in range(n):
			g[arr[i]].append(i + 1)
			if arr[i] == 0:
				q.append([i + 1, 0])
		ans = 0
		l = []
		self.sieve(2 * n)
		while q:
			(x, y) = q.popleft()
			if self.primes[x + y] and y != 0:
				ans += 1
			for i in g[x]:
				q.append([i, y + 1])
		return ans


from collections import defaultdict as dd

class Solution:
	primes = []
	count = 0

	def sieve(self, n):
		p = 2
		self.primes = [True] * (n + 1)
		while p * p <= n:
			if self.primes[p]:
				for i in range(p * p, n + 1, p):
					self.primes[i] = False
			p += 1

	def firingEmployees(self, arr, n):
		g = dd(list)
		q = []
		for i in range(n):
			g[arr[i]].append(i + 1)
			if arr[i] == 0:
				q.append([i + 1, 0])

		def iss(n):
			if n < 2:
				return False
			if n == 2 or n == 3 or n == 5:
				return True
			if n % 2 == 0 or n % 3 == 0 or n % 5 == 0:
				return False
			i = 5
			while i * i <= n:
				if n % i == 0 or n % (i + 2) == 0:
					return False
				i += 6
			return True
		ans = 0
		l = []
		self.sieve(2 * n + 2)
		while q:
			(x, y) = q.pop(0)
			if self.primes[x + y] and y != 0:
				ans += 1
			for i in g[x]:
				q.append([i, y + 1])
		return ans


import math

class Solution:

	def firingEmployees(self, arr, n):
		bosses = [list() for i in range(n)]
		for i in range(n):
			if arr[i] == 0:
				geek = i
				continue
			bosses[arr[i] - 1].append(i)
		memo = {}

		def is_prime(n):
			if n in memo:
				return memo[n]
			for i in range(2, int(math.sqrt(n)) + 1):
				if n % i == 0:
					memo[n] = False
					return False
			memo[n] = True
			return True
		ans = 0
		breadth = [(geek, 0)]
		while len(breadth) > 0:
			(rank, depth) = breadth.pop(0)
			for inferior in bosses[rank]:
				breadth.append((inferior, depth + 1))
			ans += 1 if rank != geek and is_prime(depth + rank + 1) else 0
		return ans


from math import sqrt

class Solution:

	def firingEmployees(self, arr, n):

		def isPrime(x):
			if x <= 1:
				return 0
			for i in range(2, int(sqrt(x)) + 1):
				if x % i == 0:
					return 0
			return 1
		dic = {}
		start = 0
		for i in range(n):
			if arr[i] not in dic:
				dic[arr[i]] = []
			dic[arr[i]].append(i + 1)
			if arr[i] == 0:
				start = i + 1
		q = []
		q.append(start)
		(level, sum, cnt) = (0, 0, 0)
		while len(q) != 0:
			f = len(q)
			for k in range(f):
				tt = q.pop(0)
				if isPrime(tt + level) == 1 and tt != start:
					cnt += 1
				if tt in dic:
					for it in dic[tt]:
						q.append(it)
			level += 1
		return cnt


class Solution:

	def firingEmployees(self, arr, n):

		def isprime(n):
			if n == 1:
				return False
			if n == 2 or n == 3:
				return True
			if n % 2 == 0 or n % 3 == 0:
				return False
			i = 5
			while i * i <= n:
				if n % i == 0 or n % (i + 2) == 0:
					return False
				i += 6
			return True
		blacklist = 0
		que = []
		adj = [[] for _ in range(n + 1)]
		for i in range(n):
			adj[arr[i]].append(i + 1)
			if arr[i] == 0:
				que.append((i + 1, 0))
		while que:
			(rank, parent) = que.pop(0)
			if parent and isprime(rank + parent):
				blacklist += 1
			for i in adj[rank]:
				que.append((i, parent + 1))
		return blacklist


from collections import defaultdict

class Solution:

	def firingEmployees(self, arr, n):
		child_dic = defaultdict(list)
		for i in range(n):
			if arr[i] != 0:
				child_dic[arr[i]].append(i + 1)
			else:
				root = i + 1
		count = 0
		depth = 1
		curr_level = child_dic[root]
		next_level = []
		while curr_level:
			tmp = curr_level.pop()
			next_level.extend(child_dic[tmp])
			count += 1 if Solution.checkPrime(tmp + depth) else 0
			if not curr_level:
				depth += 1
				curr_level = next_level[:]
				next_level = []
		return count

	def checkPrime(num):
		isPrime = True
		for d in range(2, int(num ** 0.5) + 1):
			if num % d == 0:
				isPrime = False
				break
		return isPrime


import math
import collections

class Solution:

	def isprime(self, num):
		return self.primes[num] == 1

	def genp(self, n):
		(self.primes[0], self.primes[1]) = (0, 0)
		for i in range(2, int(math.sqrt(n)) + 1):
			if self.primes[i] == 1:
				for j in range(2, n):
					if i * j >= n:
						break
					self.primes[i * j] = 0

	def dob(self, root, adjm, lvl):
		bfs = [root]
		lvl = 0
		while bfs:
			nxt = []
			for child in bfs:
				if lvl != 0 and self.isprime(child + lvl):
					self.countb1 += 1
				if child in adjm:
					nxt = nxt + adjm[child]
			lvl += 1
			bfs = nxt

	def firingEmployees(self, arr, n):
		self.primes = [1] * (2 * n + 1)
		self.genp(2 * n + 1)
		adjm = {}
		root = -1
		for (idx, sn) in enumerate(arr):
			if sn not in adjm:
				adjm[sn] = []
			if sn == 0:
				root = idx + 1
			adjm[sn].append(idx + 1)
		self.countb1 = 0
		self.dob(root, adjm, 0)
		return self.countb1


from math import sqrt

class Solution:

	def firingEmployees(self, arr, n):

		def checkprime(ele):
			if ele == 0 or ele == 1:
				return False
			else:
				for i in range(2, int(sqrt(ele)) + 1):
					if ele % i == 0:
						return False
			return True
		m = {}
		for i in range(n):
			if arr[i] in m:
				m[arr[i]].append(i + 1)
			else:
				m[arr[i]] = [i + 1]
		q = [0]
		dp = [0 for i in range(n + 1)]
		res = 0
		while q:
			temp = []
			while q:
				ele = q.pop(0)
				if ele in m:
					for j in m[ele]:
						dp[j] = dp[ele] + 1
						if ele != 0 and checkprime(j + dp[ele]):
							res += 1
						temp.append(j)
			q = temp
		return res


class Solution:

	def __init__(self):
		self.primes = [True] * 100010
		self.primes[0] = False
		self.primes[1] = False
		for i in range(2, 100010):
			for j in range(i + i, 100010, i):
				self.primes[j] = False

	def firingEmployees(self, arr, n):
		from collections import deque
		root = -1
		graph = [[] for i in range(n)]
		for i in range(n):
			if arr[i] == 0:
				root = i
			else:
				graph[arr[i] - 1].append(i)
		visited = [False] * n
		q = deque()
		q.append(root)
		all_counts = []
		levels = [0] * n
		levels[root] = 0
		while q:
			u = q.popleft()
			for v in graph[u]:
				if not visited[v]:
					levels[v] = levels[u] + 1
					visited[v] = True
					q.append(v)
					all_counts.append(v + 1 + levels[v])
		cnt = 0
		for count in all_counts:
			if self.primes[count]:
				cnt += 1
		return cnt
if __name__ == '__main__':
	t = int(input())
	ob = Solution()
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		print(ob.firingEmployees(arr, n))
	exit(0)


import math
import collections

class Solution:

	def isPrime(self, num):
		return self.primes[num] == 1

	def buildPrimes(self, n):
		(self.primes[0], self.primes[1]) = (0, 0)
		for i in range(2, int(math.sqrt(n)) + 1):
			if self.primes[i] == 1:
				for j in range(2, n):
					if i * j >= n:
						break
					self.primes[i * j] = 0

	def searchStock(self, root, dic, level):
		stack = [root]
		level = 0
		while stack:
			nxt = []
			for child in stack:
				if level != 0 and self.isPrime(child + level):
					self.cnt += 1
				if child in dic:
					nxt = nxt + dic[child]
			level += 1
			stack = nxt

	def firingEmployees(self, arr, n):
		self.primes = [1] * (2 * n + 1)
		self.buildPrimes(2 * n + 1)
		dic = {}
		root = -1
		for (idx, val) in enumerate(arr):
			if val not in dic:
				dic[val] = []
			if val == 0:
				root = idx + 1
			dic[val].append(idx + 1)
		self.cnt = 0
		self.searchStock(root, dic, 0)
		return self.cnt


from collections import deque

class Solution:

	def sieve(self, prime, arr, n):
		p = 2
		while p * p < n:
			if prime[p] == True:
				for i in range(p * p, n + 1, p):
					prime[i] = False
			p += 1

	def firingEmployees(self, arr, n):
		prime = [True] * (n + n)
		self.sieve(prime, arr, 2 * n - 1)
		child = {}
		senior = {}
		root = -1
		size1 = 0
		for i in range(n):
			if arr[i] != 0:
				if arr[i] in child:
					child[arr[i]].append(i + 1)
				else:
					size1 += 1
					child[arr[i]] = [i + 1]
			else:
				root = i + 1
				senior[i + 1] = 0
		dq = deque()
		dq.append(root)
		size = 1
		count = 0
		while size > 0:
			val = dq.popleft()
			size -= 1
			if val not in child:
				continue
			for i in child[val]:
				senior[i] = senior[val] + 1
				dq.append(i)
				size += 1
				if prime[senior[i] + i]:
					count += 1
		return count


from collections import defaultdict, deque

class Solution:

	def firingEmployees(self, arr, n):
		sieve = [True] * (2 * n + 1)
		sieve[0] = sieve[1] = False
		for i in range(2, len(sieve)):
			if sieve[i]:
				for j in range(i * i, len(sieve), i):
					sieve[j] = False
		graph = defaultdict(list)
		for (i, parent) in enumerate(arr):
			rank = i + 1
			graph[parent].append(rank)
		q = deque()
		q.append((graph[0][0], 0))
		while q:
			(rank, parent) = q.popleft()
			arr[rank - 1] = rank + parent
			for child in graph[rank]:
				q.append((child, parent + 1))
		arr[graph[0][0] - 1] = 1
		count = 0
		for i in arr:
			if sieve[i]:
				count += 1
		return count


from collections import deque

class Solution:

	def firingEmployees(self, arr, n):
		N = 2 * n + 1
		dp = [True for _ in range(N)]
		for i in range(2, N):
			if dp[i]:
				for j in range(2 * i, N, i):
					dp[j] = False
		dp[0] = False
		dp[1] = False
		adj = {}
		for i in range(1, n + 1):
			if arr[i - 1] not in adj:
				adj[arr[i - 1]] = []
			adj[arr[i - 1]].append(i)
		cnt = 0
		queue = deque()
		queue.append([adj[0][0], 0])
		while queue:
			(v, p) = queue.popleft()
			if p != 0:
				t = v + p
				if dp[t]:
					cnt += 1
			if v in adj:
				for nv in adj[v]:
					queue.append([nv, p + 1])
		return cnt


import math
import collections

class Solution:

	def isPrime(self, num):
		return self.primes[num] == 1

	def generatePrime(self, n):
		(self.primes[0], self.primes[1]) = (0, 0)
		for i in range(2, int(math.sqrt(n)) + 1):
			if self.primes[i] == 1:
				for j in range(2, n):
					if i * j >= n:
						break
					self.primes[i * j] = 0

	def doBFS(self, root, adjMap, lvl):
		bfs = [root]
		lvl = 0
		while bfs:
			nxt = []
			for child in bfs:
				if lvl != 0 and self.isPrime(child + lvl):
					self.countBl += 1
				if child in adjMap:
					nxt = nxt + adjMap[child]
			lvl += 1
			bfs = nxt

	def firingEmployees(self, arr, n):
		self.primes = [1] * (2 * n + 1)
		self.generatePrime(2 * n + 1)
		adjMap = {}
		root = -1
		for (idx, sn) in enumerate(arr):
			if sn not in adjMap:
				adjMap[sn] = []
			if sn == 0:
				root = idx + 1
			adjMap[sn].append(idx + 1)
		self.countBl = 0
		self.doBFS(root, adjMap, 0)
		return self.countBl


import math
from collections import defaultdict

class Solution:

	def firingEmployees(self, arr, n):

		def is_prime(num):
			for i in range(2, int(math.sqrt(num)) + 1):
				if num % i == 0:
					return False
			return True
		seniors = defaultdict(list)
		start = 1
		for i in range(n):
			if arr[i] == 0:
				start += i
			else:
				seniors[arr[i]].append(i + 1)
		q = seniors[start]
		level = 1
		ans = 0
		while q:
			temp = []
			while q:
				node = q.pop()
				if is_prime(node + level):
					ans += 1
				for i in seniors[node]:
					temp.append(i)
			q = temp
			level += 1
		return ans


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def firingEmployees(self, arr, n):
		from collections import defaultdict, deque
		adj = defaultdict(list)
		vis = [False for i in range(n)]
		idx = -1
		for i in range(n):
			if arr[i] == 0:
				idx = i
			else:
				adj[arr[i] - 1].append(i)
		co = [0 for i in range(n)]
		q = deque()
		q.append((idx, 0))
		vis[idx] = True
		while q:
			t = q.popleft()
			for val in adj[t[0]]:
				if not vis[val]:
					vis[val] = True
					co[val] = 1 + t[1]
					q.append((val, 1 + t[1]))

		def sol(n):
			pr = [True for i in range(n + 1)]
			pr[0] = False
			pr[1] = False
			i = 2
			while i * i <= n:
				if pr[i]:
					for j in range(i * i, n + 1, i):
						pr[j] = False
				i += 1
			return pr
		t = max(co)
		so = sol(t + n)
		ans = 0
		for i in range(n):
			if i != idx:
				if so[co[i] + i + 1]:
					ans += 1
		return ans


from collections import defaultdict, deque
from math import sqrt

class Solution:

	def firingEmployees(self, arr, n):

		def is_prime(n):
			if n <= 2:
				return True
			for i in range(2, int(sqrt(n)) + 1):
				if n % i == 0:
					return False
			return True
		vis = [0] * n
		g = defaultdict(list)
		for i in range(n):
			if arr[i] == 0:
				vis[i] = 0
				par = i
				continue
			else:
				g[arr[i] - 1].append(i)
		count = 0
		q = deque()
		q.append((par, 0))
		while q:
			size = len(q)
			for _ in range(size):
				(node, senior) = q.popleft()
				if arr[node] != 0 and is_prime(node + senior + 1):
					count += 1
				for nei in g[node]:
					if vis[nei] == 0:
						q.append((nei, senior + 1))
		return count


class Solution:

	def firingEmployees(self, arr, n):
		f = 2 * n + 1
		Primes = [0, 0] + [1] * f
		for i in range(2, int(f ** 0.5) + 1):
			if Primes[i]:
				for j in range(2, f):
					if i * j >= f:
						break
					Primes[i * j] = 0
		Map = {}
		root = -1
		for (i, par) in enumerate(arr):
			if par not in Map:
				Map[par] = []
			if par == 0:
				root = i + 1
			Map[par].append(i + 1)
		count = 0
		bfs = [root]
		lvl = 0
		while bfs:
			next = []
			for ch in bfs:
				if lvl and Primes[ch + lvl]:
					count += 1
				if ch in Map:
					next += Map[ch]
			lvl += 1
			bfs = next
		return count


class Solution(object):

	def firingEmployees(self, arr, n):
		n_fire = 0
		p = self.count_parents(arr, n)
		for i in range(n):
			if arr[i] != 0:
				if self.is_prime(p[i] + i + 1):
					n_fire += 1
		return n_fire

	def is_prime(self, n):
		if n <= 3:
			return n > 1
		if not n % 2 or not n % 3:
			return False
		i = 5
		stop = int(n ** 0.5)
		while i <= stop:
			if not n % i or not n % (i + 2):
				return False
			i += 6
		return True

	def count_parents(self, arr, n):
		p = [0] * n
		for i in range(n):
			if p[i] != 0:
				continue
			h = []
			while arr[i] != 0:
				h.append(i)
				i = arr[i] - 1
			for j in range(len(h)):
				p[h[j]] = len(h) - j
		return p


def isprime(num):
	if num == 0:
		return False
	for n in range(2, int(num ** 0.5) + 1):
		if num % n == 0:
			return False
	return True

class Solution:

	def firingEmployees(self, arr, n):
		from collections import defaultdict, deque
		d = defaultdict(list)
		geek_rank = -1
		for i in range(n):
			if arr[i] == 0:
				geek_rank = i + 1
			else:
				d[i + 1].append(arr[i])
				d[arr[i]].append(i + 1)
		visited = {i: False for i in list(d.keys())}
		q = deque()
		q.append((geek_rank, 0))
		visited[geek_rank] = True
		new_map = defaultdict(int)
		while len(q) > 0:
			(cur, level) = q.popleft()
			new_map[cur] = level
			for x in d[cur]:
				if not visited[x]:
					q.append((x, level + 1))
					visited[x] = True
		ans = 0
		for key in list(new_map.keys()):
			if key == geek_rank:
				continue
			if isprime(key + new_map[key]):
				ans += 1
		return ans


class Solution:

	def firingEmployees(self, arr, n):
		n = n * 2
		primes = [True for x in range(n + 1)]
		primes[0] = primes[1] = False
		for i in range(2, int(n ** 0.5) + 1):
			for j in range(2, n // i + 1):
				if i * j <= n:
					primes[i * j] = False
		reportees = {}
		geek = 0
		for (i, mgr) in enumerate(arr):
			if i + 1 not in reportees:
				reportees[i + 1] = set()
			if mgr not in reportees:
				reportees[mgr] = set()
			if mgr == 0:
				geek = i + 1
			reportees[mgr].add(i + 1)
		bfsq = list(reportees[geek])
		ans = 0
		nseniors = 1
		while len(bfsq) > 0:
			nextq = []
			for emp in bfsq:
				if primes[emp + nseniors]:
					ans += 1
				for reportee in reportees[emp]:
					nextq.append(reportee)
			nseniors += 1
			bfsq = nextq
		return ans


from collections import defaultdict

class Solution:

	def firingEmployees(self, arr, n):
		isprime = [True] * (2 * n)
		prime = list()
		SPF = [None] * (2 * n)

		def findprime(n):
			isprime[0] = False
			isprime[1] = False
			for i in range(2, n):
				if isprime[i]:
					prime.append(i)
					SPF[i] = i
				j = 0
				while j < len(prime) and i * prime[j] < n and (prime[j] <= SPF[i]):
					isprime[i * prime[j]] = False
					SPF[i * prime[j]] = prime[j]
					j += 1
		findprime(2 * n)
		count = 0
		graph = defaultdict(list)
		p = 0
		for i in range(n):
			if arr[i] == 0:
				p = i + 1
			else:
				graph[arr[i]].append(i + 1)
		q = [i for i in graph[p]]
		seniors = 0
		while q:
			s = len(q)
			seniors += 1
			for j in range(s):
				idx = q.pop(0)
				if isprime[idx + seniors]:
					count += 1
				for x in graph[idx]:
					q.append(x)
		return count


def sieve(n):
	prime = [True] * (n + 1)
	p = 2
	prime[0] = False
	prime[1] = False
	for p in range(2, int(n ** 0.5) + 1):
		if prime[p] == True:
			for l1 in range(p * p, n + 1, p):
				prime[l1] = False
	return prime
prime = sieve(10 ** 5)
from collections import deque

class Solution:

	def firingEmployees(self, a, n):
		ans = 0
		dis = [0] * (n + 1)
		v = [0] * (n + 1)
		ar = {i: [] for i in range(n + 1)}
		for i in range(n):
			ar[a[i]].append(i + 1)
			ar[i + 1].append(a[i])
		k = a.index(0) + 1
		q = deque([k])
		v[k] = 1
		while len(q):
			k = q.popleft()
			for i in ar[k]:
				if v[i] == 0:
					v[i] = 1
					dis[i] = 1 + dis[k]
					q.append(i)
		for i in range(n):
			if a[i] == 0:
				continue
			c = i + 1
			c += dis[i + 1]
			if prime[c]:
				ans += 1
		return ans


import math
from collections import deque

class Solution:

	def firingEmployees(self, arr, n):
		s = 0

		def isprime(n):
			prime_flag = 0
			if n > 1:
				for i in range(2, int(math.sqrt(n)) + 1):
					if n % i == 0:
						prime_flag = 1
						break
			return prime_flag
		graph = {i: [] for i in range(1, n + 1)}
		for i in range(1, n + 1):
			if arr[i - 1] == 0:
				s = i
			else:
				graph[arr[i - 1]].append(i)
		ct = 0
		lvl = 0
		q = deque()
		q.append(s)
		while q:
			n = len(q)
			for i in range(n):
				x = q.popleft()
				if lvl:
					if not isprime(lvl + x):
						ct += 1
				for j in graph[x]:
					q.append(j)
			lvl += 1
		return ct


from collections import defaultdict

def is_prime(n):
	if n == 1:
		return False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

class Solution:

	def firingEmployees(self, arr, n):
		ans = 0
		root = None
		mapp = defaultdict(list)
		for i in range(n):
			if arr[i] == 0:
				root = i + 1
				continue
			mapp[arr[i]].append(i + 1)
		q = []
		for i in mapp[root]:
			q.append(i)
		c = 1
		while len(q) > 0:
			t = q[:]
			q = []
			for i in t:
				if is_prime(c + i):
					ans += 1
				for j in mapp[i]:
					q.append(j)
			c += 1
		return ans


from collections import deque

class Solution:

	def firingEmployees(self, arr, n):
		primes = [1 for i in range(2 * n + 1)]
		primes[0] = 0
		primes[1] = 0
		for i in range(2, 2 * n + 1):
			if primes[i]:
				for j in range(i * i, 2 * n + 1, i):
					primes[j] = 0
		adj = [[] for i in range(n + 1)]
		start = -1
		for i in range(n):
			if arr[i] == 0:
				start = i + 1
			adj[arr[i]].append(i + 1)
		que = deque()
		que.append(start)
		curr = 1
		res = 0
		while que:
			k = len(que)
			for i in range(k):
				now = que.popleft()
				if now != start and primes[curr - 1 + now]:
					res += 1
				for j in adj[now]:
					que.append(j)
			curr += 1
		return res


def _sieve(M):
	primes = [False, False] + [True] * (M - 1)
	p = 2
	while p * p <= M:
		if primes[p]:
			for i in range(p * p, M + 1, p):
				primes[i] = False
		p += 1
	return primes

def _bfs(x, levels, adj):
	(todo, ntodo) = ([], [x])
	pcnt = 0
	while ntodo:
		pcnt += 1
		(todo, ntodo) = (ntodo, todo)
		while todo:
			x = todo.pop()
			for c in adj[x]:
				levels[c] = pcnt
				ntodo.append(c)

class Solution:

	def firingEmployees(self, A, N):
		adj = [[] for _ in range(N + 1)]
		for (i, v) in enumerate(A):
			adj[v - 1].append(i)
		levels = [0] * N
		root = adj[N][0]
		_bfs(root, levels, adj)
		VS = [levels[i] + i + 1 for i in range(N)]
		M = max(VS)
		primes = _sieve(M)
		ans = 0
		for i in range(N):
			if primes[VS[i]]:
				ans += 1
		if primes[VS[root]]:
			ans -= 1
		return ans


from collections import defaultdict

def compute_primes(n):
	ps = [True] * (n + 1)
	ps[0] = ps[1] = False
	for i in range(2, n + 1):
		if not ps[i]:
			continue
		for j in range(i * i, n + 1, i):
			ps[j] = False
	return ps

class Solution:

	def firingEmployees(self, arr, n):
		primes = compute_primes(10 ** 5)
		g = defaultdict(list)
		root = 0
		for (i, parent) in enumerate(arr, start=1):
			if parent == 0:
				root = i
			g[parent].append(i)
		level = 0
		q = [root]
		ans = 0
		while q:
			nq = []
			size = len(q)
			for e in q:
				nq.extend(g[e])
				if level != 0 and primes[level + e]:
					ans += 1
			level += 1
			q = nq
		return ans


from math import sqrt

class Solution:

	def firingEmployees(self, arr, n):
		pref = [-1] * n
		prime = self.sieve(n * 2 + 1)
		ans = 0
		for i in range(n):
			if pref[i] == -1:
				self.calc(i, pref, arr)
			if pref[i] != 0 and prime[pref[i] + i + 1]:
				ans += 1
		return ans

	def calc(self, i, pref, arr):
		stack = [i]
		while stack:
			curr = stack[-1]
			if arr[curr] == 0:
				pref[curr] = 0
				stack.pop()
			else:
				senior = arr[curr] - 1
				if pref[senior] == -1:
					stack.append(senior)
				else:
					pref[curr] = pref[senior] + 1
					stack.pop()

	def sieve(self, n):
		prime = [False] * 2 + [True] * (n - 1)
		for i in range(2, int(sqrt(n)) + 1):
			if prime[i]:
				for j in range(i * i, n + 1, i):
					prime[j] = False
		return prime


import math

class TreeNode:

	def __init__(self, v):
		self.value = v
		self.children = []
		self.parent = None

	def add_child(self, node):
		self.children.append(node)

class Solution:

	def firingEmployees(self, arr, n):
		prime_dic = {2: True, 3: True, 4: False, 5: True, 6: False, 7: True, 8: False, 9: False, 10: False}

		def is_prime(n):
			if n in prime_dic:
				return prime_dic[n]
			for i in range(2, int(math.sqrt(n)) + 1):
				if n % i == 0:
					prime_dic[n] = False
					return False
			prime_dic[n] = True
			return True
		root = None
		node_dic = {}
		for (i, v) in enumerate(arr):
			if i + 1 not in node_dic:
				node = TreeNode(i + 1)
				node_dic[i + 1] = node
			if v == 0:
				root = node_dic[i + 1]
				continue
			if v not in node_dic:
				parent = TreeNode(v)
				node_dic[v] = parent
			node_dic[v].add_child(node_dic[i + 1])
		ans = 0
		stack = [(root, 0)]
		while stack:
			(node, level) = stack.pop()
			if level != 0 and is_prime(level + node.value):
				ans += 1
			for child in node.children:
				stack.append((child, level + 1))
		return ans


from collections import deque
from math import sqrt, ceil

class TreeNode:

	def __init__(self, val=0, left=None, right=None):
		self.left = None
		self.right = None
		self.val = 0

class Primes:

	def __init__(self, max_prime):
		self.cache = {0: False, 1: False}

	def is_prime(self, to_test):
		if to_test not in self.cache:
			for i in range(2, int(sqrt(to_test)) + 1):
				if to_test % i == 0:
					self.cache[to_test] = False
					break
			self.cache[to_test] = self.cache.get(to_test, True)
		return self.cache[to_test]

class Solution:

	def firingEmployees(self, arr, n):
		primes = Primes(n * 2)
		graph = dict()
		for (rank, senior_rank) in enumerate(arr):
			rank += 1
			children = graph.get(senior_rank, set())
			children.add(rank)
			graph[senior_rank] = children
		count_blacklisted = 0
		stack = deque()
		for root in graph[0]:
			stack.append((root, 0))
		while stack:
			(rank, num_seniors) = stack.pop()
			if primes.is_prime(rank + num_seniors) and num_seniors > 0:
				count_blacklisted += 1
			for child in graph.get(rank, set()):
				stack.append((child, num_seniors + 1))
		return count_blacklisted


from math import inf
from collections import deque

class Solution:

	def __init__(self):
		self.prime = self.sieve(10 ** 5)

	def sieve(self, n):
		is_prime = [True] * (n + 1)
		is_prime[0] = is_prime[1] = False
		i = 2
		while i * i <= n:
			if is_prime[i]:
				for j in range(i * i, n + 1, i):
					is_prime[j] = False
			i += 1
		return is_prime

	def bfs(self, graph, src):
		n = len(graph)
		dist = [inf] * n
		Q = deque([src])
		dist[src] = 0
		while Q:
			u = Q.popleft()
			for v in graph[u]:
				dist[v] = dist[u] + 1
				Q.append(v)
		return dist

	def firingEmployees(self, arr, n):
		graph = [[] for _ in range(n)]
		root = -1
		for (ind, par) in enumerate(arr):
			if par:
				graph[par - 1].append(ind)
			else:
				root = ind
		path = self.bfs(graph, root)
		return sum((p and self.prime[p + ind + 1] for (ind, p) in enumerate(path)))


class Solution:

	def firingEmployees(self, l, n):
		pr = [1 for i in range(2 * n + 1)]
		for i in range(2, 2 * n + 1):
			if pr[i] == 1:
				j = 2
				while i * j <= 2 * n:
					pr[i * j] = 0
					j += 1
		al = [-1 for i in range(n)]
		d = {}
		st = -1
		for i in range(n):
			if l[i] == 0:
				st = i
				continue
			if l[i] - 1 in d:
				d[l[i] - 1].append(i)
			else:
				d[l[i] - 1] = [i]
		q = [(st, 0)]
		while q:
			pls = q.pop(0)
			al[pls[0]] = pls[1]
			if pls[0] not in d:
				continue
			for kt in d[pls[0]]:
				q.append((kt, pls[1] + 1))
		ans = 0
		for i in range(n):
			if al[i] == 0:
				continue
			if pr[i + 1 + al[i]]:
				ans += 1
		return ans


from collections import defaultdict as dc

class Solution:

	def firingEmployees(self, a, n):

		def prime(x):
			for i in range(2, int(x ** 0.5) + 1):
				if x % i == 0:
					return 0
			return 1
		adj = dc(list)
		for i in range(n):
			if a[i] == 0:
				root = i + 1
			adj[a[i]].append(i + 1)
		nl = []
		cl = adj[root]
		dp = 1
		ans = 0
		while cl:
			x = cl.pop()
			nl += adj[x]
			if prime(x + dp):
				ans += 1
			if not cl:
				cl = nl[:]
				nl = []
				dp += 1
		return ans


from collections import defaultdict, deque

class Solution:

	def firingEmployees(self, arr, n):
		adj = defaultdict(list)
		root = None
		for (rank, senior) in enumerate(arr):
			if senior == 0:
				root = rank + 1
			adj[senior].append(rank + 1)
		ans = 0
		q = deque()
		for emp in adj[root]:
			q.append(emp)
		level = 1
		while q:
			size = len(q)
			while size:
				emp = q.popleft()
				if self.isPrime(emp + level):
					ans += 1
				for child in adj[emp]:
					q.append(child)
				size -= 1
			level += 1
		return ans

	def isPrime(self, n):
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True


from math import sqrt

class Solution:

	def firingEmployees(self, arr, n):
		adj_mat = {}
		for i in range(n + 1):
			adj_mat[i] = []
		for i in range(len(arr)):
			adj_mat[arr[i]].append(i + 1)
		q = []
		q.append([adj_mat[0][0], 0])
		count = 0
		while q:
			temp = q.pop(0)
			if temp[1] != 0 and isprime(temp[0] + temp[1]):
				count += 1
			for j in adj_mat[temp[0]]:
				q.append([j, temp[1] + 1])
		return count

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return False