육아 당번 나누기

문제

카메론과 제이미는 오래 함께한 반려자이고, 얼마 전 아이가 태어났다. 아이를 돌보는 일은 즐겁지만 쉽지는 않다. 두 사람 모두 과학적으로 생각하는 편이라 육아도 과학적으로 풀기로 했다.

두 사람은 하루 일과를 정하면서 시간대마다 누가 아이를 맡을지 나누려고 한다. 지금까지 모든 일을 똑같이 나눠 왔으니 이번에도 각자 하루에 정확히 12시간, 즉 720분씩 아이를 맡는다.

카메론과 제이미에게는 각자 혼자 해야 하거나 혼자 하고 싶은 다른 일정이 있다. 카메론에게는 $A_C$ 개, 제이미에게는 $A_J$ 개다. 이 일정은 매일 같은 시각에 반복된다. 카메론의 일정과 제이미의 일정은 서로 겹치지 않으므로 어느 순간에도 아이를 볼 수 있는 사람이 적어도 한 명 있다.

두 사람이 원하는 하루 육아 일정의 조건은 다음과 같다.

아이를 맡은 시간은 자신의 일정과 겹치면 안 된다. 즉 카메론의 일정이 진행되는 동안에는 제이미가 아이를 맡고, 반대의 경우도 마찬가지다.
카메론과 제이미에게 각각 정확히 720분이 배정된다.
교대 횟수, 즉 아이를 맡는 사람이 바뀌는 횟수가 최소여야 한다.

예를 들어 두 사람에게 일정이 하나씩 있다고 하자. 제이미는 오전 9시부터 10시까지, 카메론은 오후 2시부터 3시까지 일정이 있다. 제이미가 자정부터 오전 6시까지와 정오부터 오후 6시까지 아이를 맡고, 카메론이 오전 6시부터 정오까지와 오후 6시부터 자정까지 맡는 방법이 있다. 이 방법은 앞의 두 조건을 만족하지만 자정, 오전 6시, 정오, 오후 6시에 교대가 일어나 모두 4번이다. 자정에 교대가 일어나면 0번도 2번도 아닌 정확히 1번으로 센다.

더 나은 방법은 카메론이 자정부터 정오까지, 제이미가 정오부터 자정까지 맡는 것이다. 이 일정도 앞의 두 조건을 만족하고 교대는 2번뿐이며, 이 값이 가능한 최솟값이다.

두 사람의 일정 목록이 주어질 때, 위 조건을 지키는 하루 육아 일정에서 교대 횟수의 최솟값을 구하라.

입력

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

각 테스트 케이스의 첫 줄에는 카메론과 제이미의 일정 개수를 나타내는 두 정수 $A_C$ 와 $A_J$ 가 주어진다. 이어서 $A_C + A_J$ 개의 줄이 주어진다. 그중 앞의 $A_C$ 개 줄에는 각각 두 정수 $C_i$ 와 $D_i$ 가 주어진다. 카메론의 $i$ 번째 일정은 자정에서 정확히 $C_i$ 분 뒤에 시작해 자정에서 정확히 $D_i$ 분 뒤에 끝나고, 길이는 $D_i - C_i$ 분이다. 뒤의 $A_J$ 개 줄에는 각각 두 정수 $J_i$ 와 $K_i$ 가 같은 형식으로 주어지며, 제이미의 일정 하나가 시작하고 끝나는 시각을 자정에서 지난 분으로 나타낸다. 이틀에 걸치는 일정은 없고, 서로 겹치는 두 일정도 없다. 한 일정이 끝나는 순간에 다른 일정이 시작되는 것은 가능하고, 그 순간에도 교대가 일어날 수 있다.

제한

$1 \le T \le 100$
모든 $i$ 에 대해 $0 \le C_i < D_i \le 24 \times 60$
모든 $i$ 에 대해 $0 \le J_i < K_i \le 24 \times 60$
모든 $i$ 에 대한 구간 $[C_i, D_i)$ 와 모든 $i$ 에 대한 구간 $[J_i, K_i)$ 를 한데 모았을 때, 그중 어떤 두 구간을 골라도 교집합이 비어 있다. 구간은 왼쪽이 닫히고 오른쪽이 열려 있어서, 바로 이어지는 두 구간은 사이에 빈 시간이 없으면서도 겹치지 않는다.
모든 $i$ 에 대한 $D_i - C_i$ 의 합은 $720$ 이하다.
모든 $i$ 에 대한 $K_i - J_i$ 의 합은 $720$ 이하다.
$0 \le A_C \le 100$ , $0 \le A_J \le 100$
$1 \le A_C + A_J \le 100$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 교대 횟수의 최솟값이다.

힌트

예제의 첫 번째 케이스는 문제에서 설명한 상황이다.

두 번째 케이스에서는 제이미가 카메론의 일정 시간을 모두 맡아야 하고, 카메론이 나머지 시간을 모두 맡아야 한다. 이 일정에서 교대는 4번 일어난다.

세 번째 케이스에서는 자정에 카메론에서 제이미로 교대가 일어난다. 일정이 없는 나머지 1438분을 어떻게 나누더라도 제이미에서 카메론으로 바뀌는 교대가 최소 한 번 필요하고, 그보다 더 많이 교대할 이유는 없다.

네 번째 케이스를 보면 같은 사람의 일정끼리도, 서로 다른 사람의 일정끼리도 맞붙어 있을 수 있다. 카메론의 일정이 자정 직전과 직후에 모두 있으므로 자정에는 교대가 없다. 대신 제이미의 두 일정 사이에 카메론이 맡는 시간을 넣어야 해서 교대가 모두 4번 필요하다. 2분과 1438분 사이에 길이 718분인 카메론의 구간을 하나만 넣는 것이 최적이고, 그 구간을 어디에 두든 교대 횟수는 달라지지 않으므로 최적 일정은 여러 개다.

다섯 번째 케이스의 최적 일정 하나는 카메론에게 100분부터 200분까지, 500분부터 620분까지, 900분부터 1400분까지를 배정하는 것이다.