G. hsq 的群
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

hsq 是一个社交达人 ， 他加入了许多群聊 。 为了更方便地了解和朋友们的共同兴趣 ， 他想要统计好友之间有多少个共同群聊 。

在这个社交网络中 ， 共有 $$$n$$$ 个人 ， 编号从 $$$1$$$ 到 $$$n$$$ 。 已知目前存在 $$$m$$$ 个群聊 ， 每个群聊的成员信息均已给出 。 现在共有 $$$q$$$ 次询问 ， 每次给出两个不同的人 $$$u$$$ 和 $$$v$$$ ， 请你计算他们两人同时出现在多少个群聊中 。

Input

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) ， 表示测试数据的组数 。

对于每组测试数据 ：

第一行包含三个整数 $$$n$$$ ， $$$m$$$ 和 $$$q$$$ （ $$$2 \le n \le 2 \cdot 10^5$$$ ， $$$1 \le m, q \le 2 \cdot 10^5$$$ ， 且 $$$m \cdot q \le 2 \cdot 10^5$$$ ） ， 分别表示总人数 、 群聊总数和询问次数 。

接下来的 $$$m$$$ 行 ， 每行描述一个群聊的信息 。 首先是一个整数 $$$k$$$ ($$$3 \le k \le n$$$) ， 表示该群聊的人数 ； 接着是 $$$k$$$ 个整数 $$$id_1 , id_2 , \dots , id_k$$$ ($$$1 \le id_i \le n$$$) ， 表示群员的编号 。 数据保证每个群聊内的编号 $$$id$$$ 严格递增且不重复 。

接下来的 $$$q$$$ 行 ， 每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u , v \le n$$$ , $$$u \ne v$$$) ， 表示一次询问 。

数据保证

所有测试数据的 $$$n$$$ 之和不超过 $$$2 \times 10^5$$$ 。

所有测试数据的 $$$k$$$ 之和不超过 $$$5 \times 10^5$$$ 。

数据保证所有测试数据的 $$$m \cdot q$$$ 之和不超过 $$$2 \times 10^5$$$

Output

对于每组测试数据的每次询问 ， 输出一行一个整数 ， 表示 $$$u$$$ 和 $$$v$$$ 共同拥有的群聊数量 。

Example
Input
1
5 2 2
3 1 2 3
3 1 2 4
1 2
1 4
Output
2
1
Note

对于样例中的第一次询问 ： 用户 $$$1$$$ 和用户 $$$2$$$ 同时出现在了第一个群聊 $$$\{1 , 2 , 3\}$$$ 和第二个群聊 $$$\{1 , 2 , 4\}$$$ 中 ， 因此共同群聊数为 $$$2$$$ 。

对于样例中的第二次询问 ： 用户 $$$1$$$ 和用户 $$$4$$$ 仅同时出现在了第二个群聊 $$$\{1 , 2 , 4\}$$$ 中 ， 因此共同群聊数为 $$$1$$$ 。