În căutarea visului său de preamărire, Lunasorab a dat peste un şirag de perle de lungime $N$, de diferite tipuri, reprezentate printr-o literă mică a alfabetului latin. Dintre acestea, perlele marcate cu $*$ sunt considerate magice. Ele se pot transforma (şi trebuie transformate) într-o perlă de orice tip nemagic. Acum Lunasorab a primit un număr natural $L$, şi ştie că dacă poate găsi o subsecvenţă de lungime cat mai mare în şiragul iniţial, formată din concatenarea repetată a unei subsecvenţe de lungime $L$ a şiragului cu ea însăşi, o poate vinde pe piaţa neagră contra unei sume considerabile (Lunasorab nu se sfieşte în a folosi metode neconvenţionale pentru a-şi atinge scopurile).

Deoarece Lunasorab nu stă prea bine la capitolul stiinţe exacte (are alte talente), vă cere vouă ajutorul.
De asemenea, fiind mai neîncrezator din fire, Lunasorab vă cere răspunsul pentru mai multe şiraguri.

Deoarece Lunasorab nu stă prea bine la capitolul stiinţe exacte (are alte talente), vă cere vouă ajutorul. De asemenea, fiind mai neîncrezator din fire, Lunasorab vă cere răspunsul pentru mai multe şiraguri.

Pentru fiecare şirag din fişierul de intrare, aflaţi cea mai lungă subsecvenţă a şiragului, care se poate obţine prin concatenarea unei subsecvenţe de lungime $L$.