有 $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$ 个条件中至少 $k-1$ 个条件的顶点个数。

输入格式

第一行包含一个整数 $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$。

输出格式

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

样例

输入

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

输出

5
7