Taco Barrier Challenge

You are given several test cases, each containing a set of intervals on a straight line. Your task is to determine the minimum number of barriers required to block all the invading intervals.

Each test case provides an integer \(N\) indicating the total number of sections (this may be used as context but is not directly necessary for the solution) and an integer \(M\) representing the number of intervals. Following this, there are \(M\) pairs of integers \(L\) and \(R\) which represent an interval. A barrier placed at point \(x\) will block an interval if \(L \le x \le R\).

The problem can be solved optimally by using a greedy strategy, where you sort the intervals by their right endpoint and then choose barriers such that each barrier covers as many intervals as possible. For instance, for intervals \((1,2)\), \((2,3)\), and \((3,5)\), placing a barrier at 2 and another at 5 will suffice, resulting in a minimum of 2 barriers.

inputFormat

The input starts with a single integer \(T\) representing the number of test cases. Each test case begins with a line containing two integers \(N\) and \(M\), where \(N\) is the number of sections and \(M\) is the number of intervals. This is followed by \(M\) lines, each containing two integers \(L\) and \(R\) which define an interval. The input is provided via standard input (stdin).

outputFormat

For each test case, output a single integer on a new line representing the minimum number of barriers required to block all intervals. The output should be printed to standard output (stdout).

## sample

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

2
2

</p>