대한민국

대한민국은 동아시아의 한반도에 자리 잡고 있다. 삼면이 바다로, 서쪽은 서해, 동쪽은 동해, 남쪽은 남해로 둘러싸여 있다.

동해안에는 도시가 $N$개, 서해안에는 도시가 $M$개 있다. ($N \le 1000$, $M \le 1000$) 각 해안의 도시는 북쪽에서 남쪽 방향으로 $1$번부터 차례대로 번호가 매겨져 있다.

새로 취임한 대통령은 동해안과 서해안을 잇는 고속도로를 $K$개 건설하려고 한다. 각 고속도로는 동해안의 도시 하나와 서해안의 도시 하나를 곧게 잇는 직선 도로이다. (실제로는 완전히 곧은 도로가 운전자를 지루하고 피로하게 만들어 사고를 유발하므로, 일부러 고저나 커브를 두어 이를 막도록 설계한다.)

두 고속도로가 서로 교차하는 지점마다 휴게소를 짓는다. 한 지점에서 교차하는 고속도로는 최대 $2$개이다. 고속도로들이 주어졌을 때, 고속도로가 서로 교차하는 지점의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 세 정수 $N$, $M$, $K$가 주어진다. $K$는 고속도로의 개수이다.

이어지는 $K$개의 줄에는 각 고속도로의 정보가 정수 두 개로 주어진다. 첫 번째 정수는 그 고속도로가 연결하는 동해안 도시의 번호이고, 두 번째 정수는 서해안 도시의 번호이다.

고속도로의 개수는 $400{,}000$개 이하이며, 정답이 $2^{63}-1$ 이하가 되는 입력만 주어진다.

각 테스트 케이스마다 한 줄에 Test case X: Y 형식으로 출력한다. 여기서 $X$는 테스트 케이스 번호($1$부터 시작)이고, $Y$는 고속도로들이 서로 교차하는 지점의 개수이다.