Please code in java

Scheduling Classes

Andy studies at the University of California is very studious. He wants to take as many subjects as possible without any class overlap. The University doesnt impose any restriction on the number of classes taken during the semester.

He really doesnt care about what subject he takes; he likes them all! However, he wants to maximize the number of subjects he can take.

Input Format

The first line of input consists of an integer t. This is the number of days.

• For each day, the first line contains an integer n which gives the number of subjects offered on that day.
• Then next n lines follow containing the subject name (which is a string) followed by the start and end time for that subject in 24-hour format: hh: mm

For eg: Maths 10:00 11:00

Note: The timings are given in 24-hour format and the subject names do not have spaces between them.

Output Format

The output should contain t lines and each line has a number representing the maximum number of classes Andy can choose.

Constraints

* 1 <= t <= 5000 * 2 <= n <= 100 * start time of a class < end time of class 

Sample Input

2 4 Maths 16:00 18:00 ComputerScience 12:00 13:00 Physics 12:30 14:00 Chemistry 14:00 16:30 5 Geography 14:00 16:00 History 12:00 14:30 Arts 14:00 16:30 Literature 12:30 13:30 German 13:30 15:00

Sample Output

2 2