Job Scheduling

There are $N$ jobs. Each job is given by two integers $s, t$ ($s < t$), meaning the job starts at time $s$ and ends at time $t$. If the time intervals of two jobs overlap, the factory cannot perform both. (If the end time of one job equals the start time of another, the two jobs do not overlap.)

The factory wants to process as many jobs as possible. Because it can handle only one job at a time, the number of jobs it can process is limited. Instead of expanding the factory, the factory adds more jobs to the schedule.

There are $Q$ queries. In the $i$-th query, $R_i$ additional jobs are given. For each query, output the maximum number of jobs that can be processed among the $N + R_i$ jobs.

For example, let $N=4$ and $Q=2$, and let the base jobs be $\{(1, 5), (5, 10), (14, 16), (2, 9)\}$. The two queries are $\{(3, 7), (11, 14)\}$ and $\{(4, 8), (13, 15)\}$. For the first query, the optimal choice is the 4 jobs $\{(1, 5), (5, 10), (11, 14), (14, 16)\}$. For the second query, the optimal choice is the 3 jobs $\{(1, 5), (5, 10), (14, 16)\}$.

The first line contains a natural number $T$, the number of test cases ($1 \le T \le 20$). The $T$ test cases follow.

The first line of each test case contains the number of jobs $N$ ($1 \le N \le 120\,000$). Each of the next $N$ lines contains the start time and end time $s, t$ of a job ($0 \le s < t \le 10^9$).

The next line contains the number of queries $Q$ ($1 \le Q \le 60\,000$). Each query starts with a line containing the number of new jobs $R_i$ ($1 \le R_i \le 120\,000$, $1 \le \sum R_i \le 120\,000$). Each of the next $R_i$ lines contains the start time and end time $s, t$ of a new job ($0 \le s < t \le 10^9$).

The sum of $N$ over all test cases is at most $1\,300\,000$. The sum of $\sum R_i$ over all test cases is at most $1\,100\,000$.

For each test case, print a line in the form Case #$C$, where $C$ is the test case number. Then print $Q$ lines, each containing the answer to one query.