Parenting Partnering (Large)

Cameron and Jamie have been life partners for a long time, and they recently became parents. Looking after a baby is fun, but it is not easy. Both of them think like scientists, so they decided to take a scientific approach to baby care as well.

The two are putting together a daily routine and need to decide who is in charge of the baby during each part of the day. They have split everything equally so far and want to keep doing that, so each of them takes charge for exactly 12 hours (720 minutes) per day.

Each of them also has activities to do alone. Cameron has $A_C$ of them and Jamie has $A_J$ of them, and they happen at the same times every day. None of Cameron's activities overlaps any of Jamie's, so at least one parent is always free to look after the baby.

The daily schedule they want satisfies these conditions.

• Baby time must not overlap that parent's own activity. During Cameron's activities Jamie is in charge, and during Jamie's activities Cameron is in charge.
• Cameron and Jamie are each assigned exactly 720 minutes of baby time.
• The number of exchanges, meaning the number of times the person in charge changes, is as small as possible.

For example, suppose Jamie has one activity from 9 am to 10 am and Cameron has one activity from 2 pm to 3 pm. If Jamie takes the baby from midnight to 6 am and from noon to 6 pm and Cameron takes the rest, the first two conditions hold, but exchanges happen at midnight, 6 am, noon and 6 pm, so there are 4 of them. An exchange at midnight counts exactly once, not zero times and not twice. If Cameron takes the baby from midnight to noon and Jamie takes it from noon to midnight, the same two conditions hold with only 2 exchanges, and no schedule does better.

Given the activities of Cameron and Jamie, find the smallest number of exchanges a daily schedule can have.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains two integers $A_C$ and $A_J$, the number of activities of Cameron and of Jamie. Then $A_C + A_J$ lines follow. The first $A_C$ of them contain two integers $C_i$ and $D_i$, describing Cameron's $i$-th activity, which starts exactly $C_i$ minutes after midnight and ends exactly $D_i$ minutes after midnight, so it takes $D_i - C_i$ minutes. The last $A_J$ lines contain two integers $J_i$ and $K_i$ in the same format for Jamie's activities. No activity spans two days. One activity may start exactly when another ends, and an exchange can still happen at that moment.

Limits

• $1 \le T \le 100$
• $0 \le C_i < D_i \le 24 \times 60$ for all $i$
• $0 \le J_i < K_i \le 24 \times 60$ for all $i$
• Taking all intervals $[C_i, D_i)$ together with all intervals $[J_i, K_i)$, no two of them have a common point. The intervals are closed on the left and open on the right, so two consecutive activities leave no time in between yet do not overlap.
• $\sum_i (D_i - C_i) \le 720$
• $\sum_i (K_i - J_i) \le 720$
• $0 \le A_C \le 100$
• $0 \le A_J \le 100$
• $1 \le A_C + A_J \le 200$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the smallest possible number of exchanges.

In the first case of the sample, Jamie can take the baby from midnight to noon and Cameron from noon to midnight, which gives 2 exchanges.

In the second case, Jamie must cover both of Cameron's activities, and those two intervals add up to 720 minutes, so Jamie's whole share is already fixed. Cameron covers all the remaining time, and there are 4 exchanges.

In the third case, Jamie is in charge just before midnight and Cameron just after it, so one exchange happens at midnight. However the remaining 1438 minutes are split, at least one exchange in the other direction is needed, and there is no reason to add more, so the answer is 2.

The fourth case shows that activities of the same parent and of different parents can both be back to back. Cameron has an activity just before midnight and another just after it, so no exchange happens at midnight. Instead a single 718 minute interval for Jamie has to be placed inside the free time from minute 2 to minute 1438, which brings the total to 4 exchanges. The position of that interval does not change the count, so several optimal schedules exist.

In the fifth case, one optimal schedule gives Cameron the intervals from minute 100 to 200, from 500 to 620, and from 900 to 1400, for 6 exchanges.