Polycarpus got hold of a family tree. The found tree describes the family relations of *n* people, numbered from 1 to *n*. Every person in this tree has at most one direct ancestor. Also, each person in the tree has a name, the names are not necessarily unique.

We call the man with a number *a* a 1-ancestor of the man with a number *b*, if the man with a number *a* is a direct ancestor of the man with a number *b*.

We call the man with a number *a* a *k*-ancestor (*k* &gt; 1) of the man with a number *b*, if the man with a number *b* has a 1-ancestor, and the man with a number *a* is a (*k* - 1)-ancestor of the 1-ancestor of the man with a number *b*.

In the tree the family ties do not form cycles. In other words there isn't a person who is his own direct or indirect ancestor (that is, who is an *x*-ancestor of himself, for some *x*, *x* &gt; 0).

We call a man with a number *a* the *k*-son of the man with a number *b*, if the man with a number *b* is a *k*-ancestor of the man with a number *a*.

Polycarpus is very much interested in how many sons and which sons each person has. He took a piece of paper and wrote *m* pairs of numbers *v*<sub class="lower-index">*i*</sub>, *k*<sub class="lower-index">*i*</sub>. Help him to learn for each pair *v*<sub class="lower-index">*i*</sub>, *k*<sub class="lower-index">*i*</sub> the number of distinct names among all names of the *k*<sub class="lower-index">*i*</sub>-sons of the man with number *v*<sub class="lower-index">*i*</sub>.
The first line of the input contains a single integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>) — the number of people in the tree. Next *n* lines contain the description of people in the tree. The *i*-th line contains space-separated string *s*<sub class="lower-index">*i*</sub> and integer *r*<sub class="lower-index">*i*</sub> (0 ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*), where *s*<sub class="lower-index">*i*</sub> is the name of the man with a number *i*, and *r*<sub class="lower-index">*i*</sub> is either the number of the direct ancestor of the man with a number *i* or 0, if the man with a number *i* has no direct ancestor. 

The next line contains a single integer *m* (1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>) — the number of Polycarpus's records. Next *m* lines contain space-separated pairs of integers. The *i*-th line contains integers *v*<sub class="lower-index">*i*</sub>, *k*<sub class="lower-index">*i*</sub> (1 ≤ *v*<sub class="lower-index">*i*</sub>, *k*<sub class="lower-index">*i*</sub> ≤ *n*).

It is guaranteed that the family relationships do not form cycles. The names of all people are non-empty strings, consisting of no more than 20 lowercase English letters.
import sys
from collections import defaultdict

def rd(): return sys.stdin.readline().strip()
def rdl(typ,sep=" "): return list(map(typ, rd().split(sep)))
def wt(x,sep="\n") : sys.stdout.write(str(x) + sep)    # string / num
def wtBoolUp(x): wt("YES" if x else "NO")  # True = YES/ False =NO
def wtBoolLow(x): wt("Yes" if x else "No")  # True = Yes/ False =No
def wtlArr(arr,sep=" "):   # Print arr in single line
    if not arr: return
    for x in arr: wt(x, " ") 
def wtlsArr(arr):  # Print arr in mult lines
    if not arr: return
    for x in arr: wt(x)
def wtlsArrArr(arr):    # print Arrays in multiple lines
    for a in arr: wtlArr(a)

# for dfs use this and use 'yield' during dfs and at last
from types import GeneratorType
def bootstrap(f, stack=[]):              
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc


# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
''' ॐॐ _/\_ हर हर महादेव _/\_ ॐॐ '''

# sys.setrecursionlimit(300_005)
# mod = 10**9 + 7


adjList = cnt  = queries = name = []
parent = depth = heavy = isHeavy = []
res = []
## Euler Tour : 
start = end = flat = []
timer = -1


@bootstrap
def dfsSize(root, par):
    size = 1
    maxChildSize = 0
    for child in adjList[root]:
        if child == par:
            continue
        parent[child] = root
        depth[child] = 1 + depth[root]
        childSize = yield dfsSize(child, root)
        size += childSize
        if childSize > maxChildSize:
            maxChildSize = childSize
            heavy[root] = child
    yield size


@bootstrap
def add(root, par):
    global res
    cnt[depth[root]][name[root]] += 1

    for child in adjList[root]:
        if child == par or isHeavy[child]:
            continue
        yield add(child, root)
    yield


@bootstrap
def remove(root, par):
    global res
    cnt[depth[root]][name[root]] -= 1
    if cnt[depth[root]][name[root]] <= 0:
        cnt[depth[root]].pop(name[root])


    for child in adjList[root]: 
        if child == par or isHeavy[child]:
            continue
        yield remove(child, root)
    yield 


# working on the subtree of bigchild keep = 1 else keep = 0
# we have to call small child before heavy child
@bootstrap 
def dfs(root, par, keep):
    global res, timer

    heavyChild = heavy[root]

    for child in adjList[root]:   # move to light chains
        if child == par or child == heavyChild:
            continue
        yield dfs(child, root, False)

    if heavyChild != -1:
        yield dfs(heavyChild, root, 1)
        isHeavy[heavyChild] = True  # mark the heavy child

    yield add(root, par)

    for qIdx,k in queries[root]:
        res[qIdx] = len(cnt[k + depth[root]])

    # unmark heavy child of root which is marked above
    if heavyChild != -1 :
        isHeavy[heavyChild] = False

    if keep == False:
        yield remove(root, par)        
    yield



def solve():
    global adjList, cnt, queries, name
    global parent, depth, heavy, isHeavy, res
    global start, end , flat , timer

    n = int(rd())
    
    name = [None]*(n+1)
    adjList = [[] for _ in range(n+1)]
    for i in range(n):
        name[i], par = rdl(str)
        par = int(par) - 1
        if par != -1:
            adjList[par].append(i)


    queries = [[] for _ in range(n+1)]
    m = int(rd())
    for qIdx in range(m):
        node,k = rdl(int)
        node = int(node) -1
        queries[node].append((qIdx, k))

    ##  -----------------------------------------  

    cnt = [defaultdict(int) for _ in range(n+1)]
    depth = [0]*(n+1)
    heavy = [-1]*(n+1)
    isHeavy = [False]*(n+1)
    
    parent = [-1]*(n+1)
    res = [0]*m
    
    for i in range(n):
        if parent[i] != -1:
            continue
        dfsSize(i, -1)
        dfs(i, -1, True)
        remove(i, -1)     # remove the information of ith for new component

    wtlsArr(res)


# Don't forget the mod and recursion limit and INF

solve()
