Rak n Roll

Dany jest wyraz złożony z małych liter. Twoim zadaniem jest wstawienie do niego dowolnej małej litery, tak aby powstał palindrom. Litera może być wstawiona na dowolnej pozycji.

Wejście

W pierwszej linii znajduje się liczba zestawów danych t ∈ [1, 300]. W kolejnych t liniach znajdują się zestawy danych.

Każdy zestaw danych to pojedynczy wyraz składający się z małych liter alfabetu angielskiego. Jego długość nie przekracza 100 liter.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać utworzony palindrom. Jeżeli można utworzyć wiele palindromów wybieramy ten, który jest pierwszy w porządku alfabetycznym.

Jeżeli palindromu nie da się utworzyć należy wypisać słowo NIE.

Przykład

Wejście:

3
kajak
na
wodzie

Wyjście:

kajjak
ana
NIE