The Family Tree of ACM Cells

Scientists are studying the behavior of a newly discovered Agamic Cellular Microbe (ACM). This special microbe can reproduce massively on its own in a short time. The lifetime of an ACM consists of three phases:

1. The infancy phase, which starts at birth and lasts roughly several seconds;
2. The multiplication phase, in which one ACM can produce up to 100 offspring in only a few milliseconds;
3. The mature phase, in which it stays inactive for the rest of its life.

At the start of the experiment, a single newborn ACM cell is placed in an environment suitable for reproduction. This cell, numbered 0, begins to multiply, and its descendants are numbered starting from 1 according to their positions in the family hierarchy. During the experiment, special equipment records the numbers of the offspring produced by each ACM. The experiment stops after a certain period of time.

Figure 1: The family tree of the ACMs in the first case of the sample input

Your task is to determine whether one ACM is an ancestor of another.

The input contains multiple test cases. The first line holds a single integer T (1 ≤ T ≤ 20), the number of test cases. The T test cases follow, each preceded by a single blank line.

Each test case begins with a single integer N (1 ≤ N ≤ 300,000), the number of ACMs whose offspring are recorded. The next N integers Ci (0 ≤ i < N, 0 ≤ Ci ≤ 100) give the number of offspring of the i-th ACM. These integers are not necessarily on the same line. The next line holds an integer M (1 ≤ M ≤ 500,000), the number of queries. M lines follow, each with two distinct integers a and b, asking whether the a-th ACM is an ancestor of the b-th ACM.

The total number of ACMs may be larger than N, but never exceeds 2,000,000.

For each test case, print the number of queries that must be answered yes, that is, the a-th ACM is an ancestor of the b-th ACM.