Maximum Non-Overlapping Sessions Scheduling

You are given a series of test cases. In each test case, there are ( n ) sessions and ( m ) available rooms. Every session is defined by its start time and end time. Your task is to schedule as many sessions as possible such that no two sessions scheduled in the same room overlap. Two sessions are said to not overlap if the end time of one is less than or equal to the start time of the other. Formally, if a session ( i ) (with start time ( s_i ) and end time ( e_i )) and session ( j ) (with start time ( s_j ) and end time ( e_j )) are scheduled in the same room, then they must satisfy ( e_i \leq s_j ) or ( e_j \leq s_i ).

The goal is to maximize the total number of sessions scheduled across all rooms.

inputFormat

The input is read from standard input. The first line contains an integer ( T ) representing the number of test cases. Each test case begins with a line containing two integers ( n ) and ( m ) (the number of sessions and the number of rooms, respectively). This is followed by ( n ) lines, each containing two integers, representing the start time and end time of each session.

outputFormat

For each test case, output a single line containing one integer—the maximum number of sessions that can be scheduled without any overlapping sessions in any room.## sample

3
5 2
1 4
2 6
4 7
1 3
5 8
3 1
1 5
2 3
3 7
1 1
1 2

4
2
1