시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 176 64 54 38.571%

문제

"고양이와 개"는 한국에서 가장 인기있는 TV 프로그램이다. 이 프로그램에는 개와 고양이가 여러마리 출연하고, 서바이벌 방식을 통해 마지막 한마리가 "최고의 애완동물" 타이틀을 가져가게 된다. 매 에피소드마다 개와 고양이는 시청자들에게 애교를 부리고, 시청자 투표에 의해 다음 라운드에 진출하는 동물이 정해진다.

모든 시청자는 다음 라운드에 진출시킬 동물과 이번 라운드에서 떨어뜨릴 동물을 한 마리씩 투표하게 된다. 모든 사람은 고양이를 좋아하거나 (개를 싫어한다) 개를 좋아한다 (고양이를 싫어한다). 따라서, 모든 투표는 고양이 번호 하나와 개 번호 하나로 이루어져 있다.

각 시청자는 자신의 투표가 반영이 됬을 때 프로그램을 계속 시청하고, 그렇지 않은 경우에는 더 이상 프로그램을 보지 않는다. 투표가 반영되는 상황은 다음 라운드에 진출하는 동물로 뽑은 동물이 다음 라운드로 진출하는 것이고, 이번 라운드에서 탈락할 동물로 뽑은 동물이 탈락하는 것이다.

"고양이와 개"의 PD는 시청자를 최대한 많이 확보하려고 한다. 각 시청자의 투표 결과가 주어졌을 때, 다음 라운드를 시청할 시청자의 수의 최대값 (투표가 반영되는 시청자의 최대값)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 고양이의 수 c, 개의 수 d, 투표한 시청자의 수 v가 주어진다. (1 ≤ c, d ≤ 100, 0 ≤ v ≤ 500)

다음 v개 줄에는 각 시청자의 투표 정보가 주어진다. 첫 번째로 주어지는 동물은 시청자가 다음 라운드에 진출시킬 동물로 뽑은 동물이고, 두 번째는 이번 라운드에서 탈락시킬 동물이다. 동물이 고양이인 경우에는 C로 시작하고, 개인 경우에는 D로 시작한다. 다음에 주어지는 숫자는 동물의 번호이다. 고양이의 경우에 번호는 1과 c, 개는 1과 d이다. 예를 들어, D42는 42번 개이다.

출력

각 테스트 케이스 마다, 투표가 반영되는 시청자의 최대값을 출력한다.

예제 입력

2
1 1 2
C1 D1
D1 C1
1 2 4
C1 D1
C1 D1
C1 D2
D2 C1

예제 출력

1
3

힌트