Mesa redonda#13076

Mesa redonda

2 segundos
512 megabytes

estudiantes de un club de programación están sentados a una mesa redonda. Están numerados de a en sentido horario, de modo que el estudiante está sentado junto al estudiante .

El entrenador quiere formar con ellos la mayor cantidad posible de equipos. Para que los miembros de un equipo puedan discutir los problemas sin gritarse a través de toda la mesa, elaboró una lista de equipos posibles, cada uno formado por estudiantes sentados consecutivamente. Los equipos pueden tener cualquier tamaño.

El -ésimo equipo posible está dado por los números l_i y r_i: incluye a los estudiantes numerados desde l_i hasta r_i inclusive, avanzando en sentido horario. Es decir:

En particular, cuando l_i = r_i, el equipo consta de un solo estudiante, y cuando l_i = r_i + 1 o l_i = 1 y r_i = n, consta de los estudiantes. Algunos equipos de la lista pueden coincidir.

Cada estudiante puede pertenecer a lo sumo a un equipo formado. Encuentre la mayor cantidad de equipos que se pueden formar.

Entrada

La primera línea contiene un único entero (1 \le t \le 10^6) — la cantidad de casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros y (1 \le n, m \le 10^6) — la cantidad de estudiantes y la cantidad de equipos posibles.

Cada una de las siguientes líneas contiene dos enteros l_i y r_i (1 \le l_i, r_i \le n) — el -ésimo equipo posible.

Se garantiza que la suma de y la suma de sobre todos los casos de prueba no superan 10^6.

Salida

Para cada caso de prueba, imprima en una línea aparte un único entero — la mayor cantidad de equipos que se pueden formar simultáneamente.

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Nota

En el primer ejemplo:

  • En el primer caso de prueba, los equipos posibles son , y . Los equipos y se pueden formar juntos, pero los tres no, porque los dos últimos tienen en común al estudiante .

  • En el segundo caso de prueba, ambos equipos constan de los cuatro estudiantes, por lo que solo se puede formar uno.

  • En el tercer caso de prueba, se pueden formar \{1, 2, 3\}, y . No se pueden formar más.

En el segundo ejemplo, los equipos posibles son \{9, 10, 1, 2\}, \{3, 4, 5\}, \{6, 7, 8\}, \{1, 2, 3, 4\}, \{5, 6, 7\} y . Los tres primeros se pueden formar juntos, pero cuatro no.