Description

Given a rooted tree with $n$ nodes. There are $m$ queries, each query provides a pair of node numbers $x$ and $y$, asking about the ancestor-descendant relationship between $x$ and $y$.

Input Format

The first line of input contains an integer $n$ representing the number of nodes;

The next $n$ lines each contain a pair of integers $a$ and $b$ indicating there is an edge between $a$ and $b$. If $b$ is $-1$, then $a$ is the root of the tree;

The $(n+2)$-th line is an integer $m$ representing the number of queries;

The next $m$ lines each contain two positive integers $x$ and $y$, representing a query.

Output Format

For each query, if $x$ is an ancestor of $y$, output $1$; if $y$ is an ancestor of $x$, output $2$; otherwise, output $0$.

Sample 1

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

1
0
0
0
2

Data Range and Hints

For $30\%$ of the data, $1\le n,m\le 10^3$;

For $100\%$ of the data, $1\le n,m\le 4\times 10^4$, and each node's number does not exceed $4\times 10^4$.