Zolaqların Dövrləri
Hər bir M zolağı Buxarest Politexnik Universitetinin Parkında N kəsişməsindən ikisini birləşdirir (etiketlənmiş 1-dən N-ə qədər). Heç bir kəsişmə cütü birdən çox zolaqla birləşdirilmir və hər bir kəsişmədən digərinə bir və ya daha çox zolaq vasitəsilə keçmək mümkündür. Zolaqların dövrü sadədir, əgər hər bir kəsişmədən dəqiq bir dəfə keçərsə.
Universitetin rəhbərliyi zolaqlara Regional Kollektiv Proqramlaşdırma Müsabiqəsinin qaliblərinin şəkillərini yerləşdirmək istəyir ki, eyni universitetdən olan qaliblərin şəkilləri eyni sadə dövrün zolaqlarında olsun. Buna görə də, rəhbərlik ən uğurlu universitetlərə ən uzun sadə dövrləri təyin etmək istəyir. Problem ən uzun dövrləri tapmaqdır. Xoşbəxtlikdən, parkın hər bir zolağı bir sadə dövrdə iştirak edir (şəkilə baxın).
Giriş faylının birinci sətrində test hallarının sayı T veriləcək. Hər bir test halı müsbət tam ədədlər N və M ilə başlayan bir sətirlə başlayır, aralıqla ayrılmış (4 <= N <= 4444). Test halının növbəti M sətrinin hər biri bir zolaqla birləşdirilən kəsişmə cütlərinin etiketlərini ehtiva edir.
Hər bir test halı üçün çıxışda bir sətirdə maksimal sadə dövrün uzunluğunu çap edin.