Fişierul intrare/ieşire:	semipal.in, semipal.out	Sursă	ONIS 2015, Runda 1
Autor	Mihai Nitu, Murtaza Alexandru, Vlad Costin	Adăugată de	UNIBUC Impaler-009 Challenge costyv87 •The_Viper_The_Mountain_And_The_Imp
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Por Costel si Semipalindroamele

Programatorul nostru in devenire, Por Costel, tocmai s-a intors din tabara de programare de la Petrozaporksk. Acolo a invatat multe lucruri: cum sa fiarba un cocean de porumb, cum sa foloseasca tastatura sa se scarpine pe burta etc. Parca isi aminteste si o problema de programare:

Se defineste un semipalindrom ca fiind un cuvant c pentru care exista un subcuvant $w$ astfel incat $w$ este prefix al lui $c$ iar $w_r$ (cuvantul invers) este suffix al lui $c$ .

De exemplu ‘ababba’ este semipalindrom deoarece exista un subcuvant ‘ab’ prefix al cuvantului iar ‘ba’ este sufix al cuvantului.

Considerand doar semipalindroamele care contin literele ‘a’ si ‘b’, problema cerea sa gasiti al $K$ -lea lexicografic semipalindrom de lungime $N$ .
Por Costel nu isi aminteste daca enuntul era exact asa la Petrozaporksk, dar totusi problema i se pare interesanta si va roaga sa il ajutati cu ea.

Date de intrare

Fişierul de intrare semipal.in va contine pe prima linie numarul $T$ , numarul de teste, iar pe urmatoarele $T$ linii cate doua numere, $N$ si $K$ .