猴子住在树上，对吧？烈焰猴（Infernape）可能也住在树上。给定一棵包含 $n$ 个顶点的树（树是一个无环连通无向图）和 $q$ 个独立询问。顶点编号从 $1$ 到 $n$。

在每个询问中，树的顶点上有 $k$ 只烈焰猴（对于不同的询问，$k$ 可能不同）。第 $i$ 只烈焰猴位于顶点 $v_i$，其能力值为 $r_i$。烈焰猴会加热所有与 $v_i$ 距离小于或等于其能力值 $r_i$ 的顶点。两点之间的距离定义为它们在树上最短路径上的边数。能力值是非负的，因此每只烈焰猴总是会加热它所在的顶点。你的任务是计算有多少个顶点被至少 $k-1$ 只烈焰猴加热。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)，表示树的顶点数。

接下来 $n-1$ 行，第 $i$ 行描述树的一条边，包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n$)，表示这条边的两个端点。

保证给出的边构成一棵合法的树。

下一行包含一个整数 $q$ ($1 \le q$)，表示询问次数。

接下来的 $q$ 个数据块描述每个询问。

每个数据块的第一行包含一个整数 $k$ ($2 \le k \le 300\,000$)，表示当前询问中烈焰猴的数量。

接下来每个数据块包含 $k$ 行。第 $i$ 行包含两个整数 $v_i$ 和 $r_i$ ($1 \le v_i \le n, 0 \le r_i \le n-1$)，表示第 $i$ 只烈焰猴所在的顶点索引及其能力值。

所有询问中 $k$ 的总和不超过 $300\,000$。

输出格式

输出 $q$ 行。第 $i$ 行应包含第 $i$ 个询问中被至少 $k-1$ 只烈焰猴加热的顶点数量。

样例

输入 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

5
7

说明

样例测试中的树结构如下：

询问的示意图如下：

红色区域被所有烈焰猴加热，而橙色区域被除一只以外的所有烈焰猴加热。