Dəyirmi masa#13076

Dəyirmi masa

2 saniyə
512 meqabayt

Proqramlaşdırma dərnəyinin tələbəsi dəyirmi masa arxasında oturub. Onlar saat əqrəbi istiqamətində -dən -ə qədər nömrələnib, belə ki, nömrəli tələbə nömrəli tələbənin yanında oturur.

Məşqçi onlardan mümkün qədər çox komanda yaratmaq istəyir. Komanda üzvləri məsələləri bütün masa boyu bir-birinə qışqırmadan müzakirə edə bilsinlər deyə, o, hər biri ardıcıl oturan tələbələrdən ibarət olan mümkün komandanın siyahısını tərtib etdi. Komandalar istənilən ölçüdə ola bilər.

-ci mümkün komanda l_i və r_i ədədləri ilə verilir: saat əqrəbi istiqamətində hərəkət edərkən l_i-dən r_i-yə qədər (daxil olmaqla) nömrələnmiş tələbələr ona daxildir. Yəni:

Xüsusilə, l_i = r_i olduqda komanda bir tələbədən, l_i = r_i + 1 olduqda və ya l_i = 1 və r_i = n olduqda isə bütün tələbədən ibarətdir. Siyahıdakı bəzi komandalar üst-üstə düşə bilər.

Hər tələbə ən çoxu bir yaradılmış komandaya daxil ola bilər. Yaradıla bilən komandaların ən böyük sayını tapın.

Giriş

Birinci sətirdə bir tam ədəd (1 \le t \le 10^6) — test hallarının sayı verilir.

Hər test halının birinci sətrində iki tam ədəd və (1 \le n, m \le 10^6) — tələbələrin sayı və mümkün komandaların sayı verilir.

Sonrakı sətrin hər birində iki tam ədəd l_i və r_i (1 \le l_i, r_i \le n) — -ci mümkün komanda verilir.

Bütün test halları üzrə -lərin cəminin və -lərin cəminin 10^6-nı aşmadığı təmin edilir.

Çıxış

Hər test halı üçün ayrıca sətirdə bir tam ədəd — eyni anda yaradıla bilən komandaların ən böyük sayını çıxarın.

Nümunələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Qeyd

Birinci nümunədə:

  • Birinci test halında mümkün komandalar , və -dür. və komandalarını birlikdə yaratmaq olar, lakin hər üçünü yaratmaq olmaz, çünki son ikisinin ortaq nömrəli tələbəsi var.

  • İkinci test halında hər iki komanda bütün dörd tələbədən ibarətdir, buna görə yalnız birini yaratmaq olar.

  • Üçüncü test halında \{1, 2, 3\}, və komandalarını yaratmaq olar. Daha çoxunu yaratmaq mümkün deyil.

İkinci nümunədə mümkün komandalar \{9, 10, 1, 2\}, \{3, 4, 5\}, \{6, 7, 8\}, \{1, 2, 3, 4\}, \{5, 6, 7\} və -dür. Onlardan ilk üçünü birlikdə yaratmaq olar, lakin dördünü yaratmaq olmaz.