== include(page="template/taskheader" task_id="semipal") ==

%{float: right;}!problema/semipal?por_costel_computer.jpg! %
 

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 <tex>w</tex> astfel incat <tex>w</tex> este prefix al lui <tex>c</tex> iar <tex>w_r</tex>(cuvantul invers) este suffix al lui <tex>c</tex>.

h2. Date de intrare

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

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

h2. Date de ieşire

h2. Restricţii

* <tex>1</tex> &le; <tex>T</tex> &le; <tex>1000</tex>
* <tex>1</tex> &le; <tex>N</tex> &le; <tex>63</tex>

* <tex>1</tex> &le; <tex>T</tex> &le; <tex>3000</tex>
* <tex>2</tex> &le; <tex>N</tex> &le; <tex>63</tex>

* <tex>1</tex> &le; <tex>K</tex> &le; numarul de semipalindroame de lungime <tex>N</tex>
h2. Exemplu

10329