Bir programlama kulübünün öğrencisi yuvarlak bir masanın etrafında oturuyor. Saat yönünde 'den 'ye kadar numaralandırılmışlardır, dolayısıyla numaralı öğrenci numaralı öğrencinin yanında oturmaktadır.
Antrenör onlardan mümkün olduğunca çok takım oluşturmak istiyor. Takım üyeleri problemleri masanın bir ucundan diğerine bağırmadan tartışabilsinler diye, her biri ardışık oturan öğrencilerden oluşan olası takımdan bir liste hazırladı. Takımlar herhangi bir büyüklükte olabilir.
-inci olası takım l_i ve r_i sayılarıyla verilir: saat yönünde ilerlerken l_i'den r_i'ye kadar (dahil) numaralı öğrencileri içerir. Yani:
eğer l_i \le r_i ise, takım l_i, l_i + 1, \ldots, r_i öğrencilerinden oluşur;
eğer l_i > r_i ise, takım l_i, l_i + 1, \ldots, n, 1, 2, \ldots, r_i öğrencilerinden oluşur.
Özellikle, l_i = r_i olduğunda takım tek bir öğrenciden oluşur; l_i = r_i + 1 olduğunda veya l_i = 1 ve r_i = n olduğunda ise öğrencinin tamamından oluşur. Listedeki bazı takımlar aynı olabilir.
Her öğrenci en fazla bir oluşturulan takımda yer alabilir. Oluşturulabilecek en fazla takım sayısını bulun.
İlk satır bir tam sayı (1 \le t \le 10^6) içerir — test durumlarının sayısı.
Her test durumunun ilk satırı iki tam sayı ve (1 \le n, m \le 10^6) içerir — öğrenci sayısı ve olası takım sayısı.
Sonraki satırın her biri iki tam sayı l_i ve r_i (1 \le l_i, r_i \le n) içerir — -inci olası takım.
Tüm test durumları üzerinden toplamının ve toplamının 10^6'yı aşmadığı garanti edilir.
Her test durumu için ayrı bir satırda tek bir tam sayı yazdırın — aynı anda oluşturulabilecek en fazla takım sayısı.
Örnek 1
Örnek 2
Birinci örnekte:
Birinci test durumunda olası takımlar , ve 'tür. ve takımları birlikte oluşturulabilir, ancak üçü birden oluşturulamaz, çünkü son ikisinin ortak numaralı öğrencisi vardır.
İkinci test durumunda her iki takım da dört öğrencinin tamamından oluşur, bu nedenle yalnızca biri oluşturulabilir.
Üçüncü test durumunda \{1, 2, 3\}, ve oluşturulabilir. Daha fazlası oluşturulamaz.
İkinci örnekte olası takımlar \{9, 10, 1, 2\}, \{3, 4, 5\}, \{6, 7, 8\}, \{1, 2, 3, 4\}, \{5, 6, 7\} ve 'tür. Bunlardan ilk üçü birlikte oluşturulabilir, ancak dördü oluşturulamaz.