No submission language available for this problem.

Background

Special for beginners, ^_^

Description

东海岸有N个城市，西海岸有 M 个城市（N≤1000，M≤1000），将建 K 条公路。每个海岸的城市从北到南编号为 1,2，…每条高速公路都是直线，连接东海岸和西海岸的城市。建设资金由高速公路之间的交叉数决定。两个高速公路最多在一个地方交叉。请计算告诉公路之间的交叉数量。

Format

Input

输入以 T 开始，表示测试用例的数量。 每个测试用例都是 3 个整数 N、M、K。 下面的 K 行每一行都包含两个数字，表示高速公路连接的城市号。第一个数是东海岸的城市号，第二个数字是西海岸的城市号。

Output

对每个测试用例都输出“Test case x:s”，x 表示输入样例编号，s 表示交叉数。

Samples

1
3 4 4
1 4
2 3
3 2
3 1

Test case 1: 5

Limitation

1s, 1024KiB for each test case.