GATTACA#1081
Bioinformatika və Tibb İnstitutu (IBM) ölkənizdə insan da daxil olmaqla, bəzi orqanizmlərin DNT-sini öyrənir. Orqanizmin DNT-si analiz edilməzdən əvvəl, tədqiqatçılar DNT-ni hüceyrələrdən çıxarıb onu "sekvensləşdirmə" adlı bir proses vasitəsilə deşifrə etməlidirlər.
DNT ardıcıllığını deşifrə etmək üçün istifadə olunan bir üsul "shotgun sequencing" adlanır. Bu metod uzun DNT zəncirlərini müxtəlif təsadüfi surətlərə kəsərək onları daha kiçik fraqmentlərə parçalayır. Bu üsul xüsusi bir aparat ilə DNT simvollarını (A, C, G və T) ardıcıllıqla oxuyur və sonra xüsusi bir alqoritm ilə bütün ardıcıllığı bərpa edir.
Adətən, bir DNT zəncirində ardıcıllıqda iki və ya daha çox dəfə təkrarlanan bir çox seqment olur (bunlara "təkrarlanma" deyilir). Bu təkrarlanmalar shotgun sequencing metodu ilə tam təyin edilə bilmir, çünki yığma prosesi müxtəlif təkrarlardan olan iki eyni altfraqmenti ayırd edə bilmir.
İnstitutun alimləri digər, daha bahalı bir sekvens metodu ilə eyni ailəyə məxsus bir neçə bakteriyanın DNT-sini uğurla deşifrə ediblər ki, bu üsul təkrarlanma ilə bağlı problemi aradan qaldırır. Bioloqlar bunu vəsaitin israfı hesab edirlər, çünki onların fikrincə, tədqiq olunan bakteriyaların DNT-sində böyük təkrarlanan fraqmentlər yoxdur.
Bioloqlar sizdən elə bir proqram yazmağınızı istəyirlər ki, verilən DNT ardıcıllığı üçün ardıcıllıqda iki və ya daha çox dəfə təkrarlanan ən uzun alt sətiri tapsın.
Birinci sətirdə testlərin sayı olan tam ədədi verilir (1 \leq T \leq 100). Hər bir test bir sətirdən ibarətdir: DNT ardıcıllığını təsvir edən sətiri (1 \leq n \leq 1000).
Hər sətrində yalnız , , və hərfləri ola bilər.
Hər bir giriş ardıcıllığı üçün bir sətrə əvvəlcə ən uzun, ardıcıllıqda ən azı iki dəfə təkrarlanan alt sətri, bir boşluq və onun -də neçə dəfə rast gəldiyini çap edin.
Əgər maksimal uzunluqda bir neçə alt sətir varsa, onlardan leksikqrafik olaraq ən kiçiyini seçin.
Əgər -də heç bir təkrarlanma yoxdursa, "No repetitions found!" çap edin.
Nümunə 1