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:
əgər l_i \le r_i olarsa, komanda l_i, l_i + 1, \ldots, r_i tələbələrindən ibarətdir;
əgər l_i > r_i olarsa, komanda l_i, l_i + 1, \ldots, n, 1, 2, \ldots, r_i tələbələrindən ibarətdir.
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.
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.
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ə 1
Nümunə 2
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.