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ă.

Cerinţă

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.

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.

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.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $1 \leq T \leq 10$

Exemplu

parpal.in

5
aaaa
aabbaacbxxxxbc
abcabc
abbcca
cbaabccbaabc

parpal.out

DA
DA
NU
NU
DA