$N$ 个顶点构成的树。顶点编号为 $1$ 到 $N$。所有边的权重均为 $1$。

请编写程序执行以下查询：

• k v_1 r_1 v_2 r_2 ... v_k r_k：对于某个顶点 $x$，如果 $x$ 与 $v_i$ 的距离在 $r_i$ 以内（即距离小于等于 $r_i$），则称 $x$ 满足第 $i$ 个条件。在所有顶点中，输出满足至少一个给定 $k$ 个条件的顶点个数。

输入格式

第一行包含一个整数 $N$。（$1 \le N \le 100{,}000$）

接下来 $N-1$ 行，每行包含两个整数 $u, v$，表示一条边连接的两个顶点。（$1 \le u, v \le N$）

下一行包含一个整数 $M$。（$1 \le M \le 300{,}000$）

接下来 $M$ 行，每行描述一个如上所述的查询。但与题目描述不同，每个查询不是在一行内给出，而是拆成 $k+1$ 行。请参考样例输入。（$1 \le v_i \le N$，$0 \le r_i < N$，$1 \le k$）

所有查询中 $k$ 的总和不超过 $300000$。

输出格式

每个查询的结果输出一行。

样例

输入格式 1

10
1 3
6 4
9 8
1 8
3 4
2 8
10 3
4 5
8 7
2
3
8 1
3 1
3 2
2
7 3
6 0

输出格式 1

10
7