Parpal

parpal

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

Miruna are un şir de caractere şi ar vrea să ştie dacă acesta poate fi scris ca o concatenare a unor palindroame de lungime pară.
 
Dându-se un şir de caractere de lungime $N$, să se afişeze $DA$ în cazul în care şirul se poate scrie ca o concatenare de palindroame de lungime pară şi $NU$ în caz contrar.

Poveste şi cerinţă...

h2. Date de intrare

Pe prima linie a fişierului de intrare $parpal.in$ se află un număr natural $T$ reprezentând numărul de teste. Pe fiecare dintre următoarele $T$ linii se găseşte câte un şir de caractere format din literele mici ale alfabetului englez.

Fişierul de intrare $parpal.in$ ...

h2. Date de ieşire

În fişierul de ieşire $parpal.out$ se vor găsi $T$ linii. Pe fiecare linie $i$ se va scrie $DA$ în cazul în care şirul de caractere corespunzător liniei $i + 1$ din fişierul de intrare se poate scrie ca o concatenare de palindroame de lungime pară şi $NU$ în caz contrar.

În fişierul de ieşire $parpal.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ T ≤ 10$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. parpal.in |_. parpal.out |

| 5
aaaa
aabbaacbxxxxbc
abcabc
abbcca
cbaabccbaabc
| DA
DA
NU
NU
DA

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="parpal") ==

4897