Круглий стіл#13076

Круглий стіл

2 секунди
512 мегабайтів

За круглим столом сидять студентів гуртка з програмування. Вони пронумеровані від до за годинниковою стрілкою, тож студент сидить поруч зі студентом .

Тренер хоче сформувати з них якомога більше команд. Щоб члени команди могли обговорювати задачі, не перекрикуючи одне одного через увесь стіл, він склав список з можливих команд, кожна з яких складається зі студентів, що сидять підряд. Команди можуть мати будь-який розмір.

-ту можливу команду задано числами l_i і r_i: до неї входять студенти з номерами від l_i до r_i включно, якщо рухатися за годинниковою стрілкою. Тобто:

Зокрема, при l_i = r_i команда складається з одного студента, а при l_i = r_i + 1 або l_i = 1 і r_i = n — з усіх студентів. Деякі команди в списку можуть збігатися.

Кожен студент може входити щонайбільше до однієї сформованої команди. Знайдіть найбільшу кількість команд, які можна сформувати.

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 10^6) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить два цілі числа і (1 \le n, m \le 10^6) — кількість студентів і кількість можливих команд.

Кожен із наступних рядків містить два цілі числа l_i і r_i (1 \le l_i, r_i \le n) — -ту можливу команду.

Гарантується, що сума і сума по всіх тестових випадках не перевищують 10^6.

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі:

  • У першому тестовому випадку можливі команди — , і . Команди і можна сформувати разом, а всі три — не можна, бо дві останні мають спільного студента .

  • У другому тестовому випадку обидві команди складаються з усіх чотирьох студентів, тож сформувати можна лише одну.

  • У третьому тестовому випадку можна сформувати \{1, 2, 3\}, і . Більше сформувати неможливо.

У другому прикладі можливі команди — \{9, 10, 1, 2\}, \{3, 4, 5\}, \{6, 7, 8\}, \{1, 2, 3, 4\}, \{5, 6, 7\} і . Перші три з них можна сформувати разом, а чотири — не можна.