International Cancer Pathology Company(ICPC)는 종양의 병리 영상에서 암세포를 검출하는 인공지능(AI) 모델 개발에 전념하는 회사이다. 전처리 단계에서 AI 모델은 병리 영상의 세포핵을 검출하고, 그림 12처럼 각 세포핵을 감싸는 이른바 “경계 상자”를 사용한다. 경계 상자는 4-튜플 $(x_1,y_1,x_2,y_2)$로 표현되는 직사각형이며, $(x_1,y_1)$은 왼쪽 위 꼭짓점의 좌표이고 $(x_2,y_2)$는 오른쪽 아래 꼭짓점의 좌표이다. AI 모델이 그린 경계 상자를 검출된 경계 상자라고 한다.

그림 12: 검출된 경계 상자가 있는 병리 영상.*

AI 모델의 성능을 평가하기 위해 ICPC 연구원들은 테스트 데이터(병리 영상)를 준비하며, 의료 전문가들이 미리 경계 상자로 테스트 데이터의 정답(실제 세포핵)을 표시하도록 돕는다. 이 경계 상자들을 정답 경계 상자라고 한다. 그다음 연구원들은 AI 모델로 테스트 데이터 집합의 세포핵을 검출하여 정답 세포핵이 얼마나 검출되었는지 확인한다. 정답 경계 상자가 $G$인 세포핵에 대해, $G$의 넓이의 적어도 절반만큼 $G$와 겹치는 검출된 경계 상자 $D$가 존재하면, 즉 $|D\cap G|/|G|\ge1/2$이면 AI 모델이 그 세포핵을 검출했다고 한다. 하나의 검출된 경계 상자가 둘 이상의 정답 경계 상자와 겹칠 수 있지만, 이 검출된 경계 상자에 의해 검출되었다고 할 수 있는 것은 그중 하나뿐이다. 그림 13은 정답 경계 상자와 검출된 경계 상자의 예를 보여 준다. 또한 세포핵의 크기가 제한되어 있으므로 경계 상자의 너비와 높이에도 상한이 있다.

정답 경계 상자 집합과 검출된 경계 상자 집합이 주어졌을 때, 검출된 세포핵의 최대 수를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에는 테스트 케이스 수를 나타내는 정수 $t$가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 공백으로 구분된 두 정수 $m$과 $n$이 주어지며, 각각 정답 경계 상자와 검출된 경계 상자의 수를 나타낸다. 이어지는 $m+n$개 줄은 경계 상자 좌표의 4-튜플 $(x_1,y_1,x_2,y_2)$를 나타내며, 인접한 두 정수는 공백으로 구분된다. 처음 $m$개 줄은 정답 경계 상자이고, 다음 $n$개 줄은 검출된 경계 상자이다.

• 그림의 영상은 다음 URL의 논문에서 인용하였다: https://www.kitware.com/cell-nuclei-detection-on-whole-slide-histopathology-images-using-histomicstk-and-faster-r-cnn-deep-learning-models/

그림 13: 정답 경계 상자(파란 상자)와 검출된 경계 상자(초록 상자)가 있는 병리 영상.*

제한

• $1\le t\le5$.

• $1\le m,n\le50\,000$.

• $0\le x_1,y_1,x_2,y_2\le2000$.

• 변수 $t,m,n,x_1,y_1,x_2,y_2$는 정수이다.

• 경계 상자의 너비와 높이의 최대 길이는 4이다.

• 어떤 두 정답 경계 상자도 한쪽이 다른 쪽을 포함하는 포함 관계에 있지 않으며, 검출된 경계 상자들 사이에도 그러한 관계가 없다.

출력

각 테스트 케이스마다 정수 $k$ 하나를 한 줄에 출력한다. $k$는 주어진 검출된 경계 상자들로 검출한 세포핵의 최대 수이다.

예제

입력 1

3
2 2
1 1 3 3
3 3 5 5
2 2 4 4
4 4 6 6
2 3
1 1 3 3
3 3 5 5
1 3 3 5
2 1 4 5
3 1 5 3
3 3
1 1 2 2
2 2 3 3
3 3 4 4
1 1 3 3
2 2 4 4
3 3 5 5

출력 1

0
1
3