Parenting Partnering

Cameron and Jamie are longtime life partners, and they recently became parents. Being in charge of a baby is exciting, and it is not without challenges. Both parents have a scientific mind, so they decided to take a scientific approach to baby care.

Cameron and Jamie are establishing a daily routine and need to decide who is in charge of the baby at each time of the day. They have been equal partners their whole relationship and do not want to stop now, so each of them is in charge for exactly 12 hours (720 minutes) per day.

Cameron and Jamie have other activities that they either need or want to do on their own. Cameron has $A_C$ of these and Jamie has $A_J$. These activities always take place at the same times each day. None of Cameron's activities overlap with Jamie's activities, so at least one of the parents is always free to take care of the baby.

Cameron and Jamie want a daily baby care schedule with these properties:

• Scheduled baby time must not interfere with a scheduled activity. That is, during Cameron's activities, Jamie has to be in charge of the baby, and vice versa.
• Each of Cameron and Jamie must have exactly 720 minutes assigned to them.
• The number of exchanges, that is, the number of times the person in charge of the baby changes from one partner to the other, must be as small as possible.

For example, suppose that Jamie and Cameron have a single activity each: Jamie has a morning activity from 9 am to 10 am, and Cameron has an afternoon activity from 2 pm to 3 pm. One possible but suboptimal schedule is for Jamie to take care of the baby from midnight to 6 am and from noon to 6 pm, and for Cameron to take care of the baby from 6 am to noon and from 6 pm to midnight. That fulfills the first two conditions and requires a total of 4 exchanges, which happen at midnight, 6 am, noon and 6 pm. If there is an exchange happening at midnight, it is counted exactly once, not zero or two times.

A better option is for Cameron to take care of the baby from midnight to noon, and Jamie to take care of the baby from noon to midnight. This schedule also fulfills the first two conditions, but it uses only 2 exchanges, which is the minimum possible.

Given Cameron's and Jamie's lists of activities and the restrictions above, what is the minimum possible number of exchanges in a daily schedule?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

Each test case starts with a line containing two integers $A_C$ and $A_J$, the number of activities that Cameron and Jamie have, respectively. Then, $A_C + A_J$ lines follow. The first $A_C$ of these lines contain two integers $C_i$ and $D_i$ each. The $i$-th of Cameron's activities starts exactly $C_i$ minutes after the start of the day at midnight and ends exactly $D_i$ minutes after the start of the day at midnight, taking exactly $D_i - C_i$ minutes. The last $A_J$ of these lines contain two integers $J_i$ and $K_i$ each, representing the starting and ending time of one of Jamie's activities, in minutes counting from the start of the day at midnight, in the same format as Cameron's. No activity spans two days, and no two activities overlap. One activity might end exactly as another starts, and an exchange can still occur at that time.

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$.
• Any two of the intervals of $\{[C_i, D_i)$ for all $i\}$ union $\{[J_i, K_i)$ for all $i\}$ have an empty intersection. The intervals are closed on the left and open on the right, which ensures that two exactly consecutive intervals have nothing in between but do not overlap.
• The sum of $D_i - C_i$ over all $i$ is at most $720$.
• The sum of $K_i - J_i$ over all $i$ is at most $720$.
• $0 \le A_C \le 100$, $0 \le A_J \le 100$
• $1 \le A_C + A_J \le 100$

For each test case, output one line containing Case #x: y, where x is the test case number starting from 1, and y is the minimum possible number of exchanges, as described in the statement.

The first case of the sample is the one described in the statement.

In the second case, Jamie must cover for all of Cameron's activity time, and then Cameron must cover all the remaining time. This schedule entails four exchanges.

In the third case, there is an exchange at midnight, from Cameron to Jamie. No matter how the parents divide up the remaining 1438 non-activity minutes of the day, there must be at least one exchange from Jamie to Cameron, and there is no reason to add more exchanges than that.

In the fourth case, note that back-to-back activities can exist for the same partner or for different partners. There is no exchange at midnight because Cameron has activities both right before and right after that time. However, the schedule needs to add some time for Cameron in between Jamie's activities, requiring a total of 4 exchanges. It is optimal to add a single interval for Cameron of length 718 somewhere between minutes 2 and 1438, and the exact position of that added interval does not change the number of exchanges, so there are multiple optimal schedules.

In the fifth case, one optimal schedule assigns Cameron the intervals, in minutes, 100 to 200, 500 to 620, and 900 to 1400.