777. Monu Bhaiya's Contest and Laptop Requirement

0

Medium

Monu Bhaiya, an exceptional instructor at Coding Blocks known for his remarkable mentoring skills, has decided to test the coding abilities of his hardworking students by organizing a coding contest. However, the students are not available at the same time, as their arrival and departure times vary. Monu Bhaiya needs to ensure that all students can attempt the contest without any waiting time. To achieve this, he needs to determine the minimum number of laptops he should purchase for the contest. Your task is to assist him in this endeavor.

Input Format

The first line of input consists of a single integer T denoting the number of test cases.

The next line contains an integer N, representing the number of students.

Subsequently, the next line contains the arrival and departure times (Ai and Di) of the students, where i ranges from 0 to n-1.

The next line contains an integer N, representing the number of students.

Subsequently, the next line contains the arrival and departure times (Ai and Di) of the students, where i ranges from 0 to n-1.

Output Format

Display the minimum number of laptops required for each test case, separated by a newline.

Example

Input

1
6
900 940 950 1100 1500 1800
910 1200 1120 1130 1900 2000

Output

3

Constraints

0 < A[i] <= 2400,

A[i] < D[i], where 0<=i

A[i] < D[i], where 0<=i

Loading...

View Submissions

Console