Vasya就读的学校正在筹备毕业典礼。计划的表演之一是一场舞会,由一对男孩和女孩参加。
每个班级必须在舞会上表演两对情侣。在 Vasya 的班级中,$$$a$$$ 男生和 $$$b$$$ 女生希望参加。但并非所有男孩和女孩都准备好双人跳舞。
正式来说,你知道 $$$k$$$ 可能的一男一女对。您需要选择其中两对,以便没有人出现在超过一对中。
例如,如果 $$$a=3$$$、$$$b=4$$$、$$$k=4$$$ 和情侣 $$$(1, 2)$$$、$$$(1, 3)$$$、$$$(2, 2)$$$、$$$(3, 4)$$$ 准备一起跳舞(在每一对中,男孩的号码排在第一位,然后是女孩的号码),那么以下两对的组合是可能的(下面并未列出所有可能的选项):
- $$$(1, 3)$$$ 和 $$$(2, 2)$$$;
- $$$(3, 4)$$$ 和 $$$(1, 3)$$$;
但以下组合是不可能的:
- $$$(1, 3)$$$ 和 $$$(1, 2)$$$ - 第一个男孩进入两对;
- $$$(1, 2)$$$ 和 $$$(2, 2)$$$ - 第二个女孩进入两对;
找出选择符合上述条件的两对的方法数。如果两条路由不同的对组成,则认为它们是不同的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含三个整数 $$$a$$$、$$$b$$$ 和 $$$k$$$ ($$$1 \le a, b, k \le 2 \cdot 10^5$$$) - 班级中男孩和女孩的数量以及准备一起跳舞的情侣数量。
每个测试用例的第二行包含 $$$k$$$ 整数 $$$a_1, a_2, \ldots a_k$$$。 ($$$1 \le a_i \le a$$$),其中 $$$a_i$$$ 是编号为 $$$i$$$ 的配对中男孩的编号。
每个测试用例的第三行包含 $$$k$$$ 整数 $$$b_1, b_2, \ldots b_k$$$。 ($$$1 \le b_i \le b$$$),其中 $$$b_i$$$ 是编号为 $$$i$$$ 的配对中女孩的编号。
保证所有测试用例的 $$$a$$$、$$$b$$$ 和 $$$k$$$ 之和不超过 $$$2 \cdot 10^5$$$。
保证每一对在一个测试用例中最多指定一次。
输出
对于每个测试用例,在单独的行上打印一个整数 - 选择符合上述条件的两对的方法数。
示例
输入 #1
3 3 4 4 1 1 2 3 2 3 2 4 1 1 1 1 1 2 2 4 1 1 2 2 1 2 1 2
输出 #1
4 0 2
注意
在第一个测试用例中,以下配对组合适合:
- $$$(1, 2)$$$ 和 $$$(3, 4)$$$;
- $$$(1, 3)$$$ 和 $$$(2, 2)$$$;
- $$$(1, 3)$$$ 和 $$$(3, 4)$$$;
- $$$(2, 2)$$$ 和 $$$(3, 4)$$$。
第二个测试用例中只有一对。
在第三个测试用例中,以下配对组合适合:
- $$$(1, 1)$$$ 和 $$$(2, 2)$$$;
- $$$(1, 2)$$$ 和 $$$(2, 1)$$$。