给定一个包含 n 个人（从 1 到 n 编号）的树形社交网络。如果一个人在某天收到了一条消息，则下一天他会将消息传递给所有与他有直接社交关系的人。

现在有 m 次询问，每次询问假定第 0 天 x 号人收到了一条消息，请你计算第 k 天时新收到此条消息的人数（即第 k 天前收到过此条消息的人不计入其中）。不同询问间互不影响。

本题包含多组测试数据。

第一行一个整数 T，为测试数据组数。

对于每组测试数据：

第一行两个数 n,m 分别表示树形社交网络的人数和询问的数量。

接下来 n - 1 行，每行两个数 a, b，表示 a 号人和 b 号人之间有直接社交关系。保证输入的是树形社交网络。

接下来 m 行，每行两个数 x, k，意义见题目描述。

对于每组测试数据：输出 m 行，每行一个数表示询问的答案。

样例解释

第一个询问，第一天新收到消息的人只有 2 号。 第二个询问，第一天新收到消息的人有 1、3 号，第二天新收到消息的人有 4 号。

数据范围与约定

对于测试点 1：1\le n, m\le 10。
对于测试点 2：1\le n, m\le 100。
对于测试点 3：1\le n, m\le 1000。
对于测试点 4\sim6：1\le n, m\le 10^5, k\le 20。
对于测试点 7\sim10：1\le n, m\le 10^5。
对于所有测试点：1\le T\le 5, 1\le x\le n, 0\le k < n。

联合省选