小青鱼（Little Cyan Fish），又名 Xiao Qingyu，是 Memoria Land 的总统。Memoria Land 由 $n$ 个城市组成，编号为 $1$ 到 $n$。共有 $n-1$ 条道路，其中第 $i$ 条道路连接城市 $u_i$ 和 $v_i$。保证任意两个城市之间都有路径相连。换句话说，Memoria Land 可以看作一棵有 $n$ 个顶点的树。两个城市 $x$ 和 $y$ 之间的距离，记作 $dis(x, y)$，定义为连接这两个城市的最短路径上的边数。特别地，我们有 $dis(x, x) = 0$，因为空路径满足要求。

随着 Memoria Land 周年纪念日的临近，小青鱼计划在选定的城市放映电影以纪念这一特殊时刻。对于城市 $x$ 的居民，当且仅当城市 $y$ 正在放映电影且 $dis(x, y) \le k$ 时，他们可以前往城市 $y$ 看电影。

现在小青鱼希望制定放映电影的计划。他共有 $q$ 个问题，对于第 $i$ 个问题，他想知道如果所有编号在 $l_i$ 到 $r_i$ 之间的城市都放映电影，有多少个城市能够看到电影。

小青鱼处理 Memoria Land 的所有事务已经非常疲惫，没有精力回答这些问题了。请帮助小青鱼回答所有这些问题。

输入格式

输入包含多个测试用例。输入的第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含三个整数 $n, k, q$ ($1 \le n \le 10^5, 1 \le k \le 20, 1 \le q \le 5 \times 10^5$)。

接下来的 $n-1$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示树中连接顶点 $u_i$ 和 $v_i$ 的一条边。

接下来的 $q$ 行描述所有查询。第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)，表示一个查询。

保证： 所有测试用例的 $n$ 之和不超过 $5 \times 10^5$。 所有测试用例的 $q$ 之和不超过 $5 \times 10^5$。 * 所有测试用例的 $n \cdot k$ 之和不超过 $2 \times 10^6$。

输出格式

对于每个查询，输出一行，包含一个整数，表示答案。

样例

输入 1

2
5 1 2
1 2
1 3
2 4
2 5
2 2
2 3
8 2 3
1 2
1 3
2 4
2 5
4 6
5 7
7 8
2 2
2 5
3 4

输出 1

4
5
7
8
6