F. Кормление кошек
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Существует увлекательная игра, в которой вам нужно кормить кошек, которые приходят и уходят. Уровень игры состоит из $$$n$$$ шагов. Есть $$$m$$$ кошек; кошка $$$i$$$ присутствует на шагах от $$$l_i$$$ до $$$r_i$$$, включительно. На каждом шаге вы можете покормить всех кошек, которые в данный момент присутствуют, или ничего не делать.

Если вы кормите одну и ту же кошку более одного раза, она переест, и вы сразу проиграете игру. Ваша цель — покормить как можно больше кошек, не заставив ни одну из них переесть.

Найдите максимальное количество кошек, которых вы можете покормить.

Формально вы должны выбрать несколько целочисленных точек из отрезка от $$$1$$$ до $$$n$$$ так, чтобы среди данных отрезков ни один не покрывал две или более из выбранных точек и как можно больше отрезков покрывали одну из выбранных точек.

Входные данные

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Затем следуют описания наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m\le 2\cdot 10^5$$$).

$$$i$$$-я из следующих $$$m$$$ строк содержит пару целых чисел $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

Сумма $$$n$$$ для всех тестов не превышает $$$10^6$$$, сумма $$$m$$$ для всех тестов не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество кошек, которых вы можете покормить.

Пример
Входные данные
3
15 6
2 10
3 5
2 4
7 7
8 12
11 11
1000 1
1 1000
5 10
1 2
3 4
3 4
3 4
3 4
1 1
1 2
3 3
3 4
3 4
Выходные данные
5
1
10
Примечание

В первом примере один из способов покормить пять кошек — это покормить их на шагах $$$4$$$ и $$$11$$$.

  • На шаге $$$4$$$ будут покормлены кошки $$$1$$$, $$$2$$$ и $$$3$$$.
  • На шаге $$$11$$$ будут покормлены кошки $$$5$$$ и $$$6$$$.