За рядком малих літер у діапазоні ['a'..'z'] визначте індекс символу, який можна видалити, щоб зробити рядок паліндромом. При наявності декількох варіантів вибору індексу, виберіть будь-який.

Якщо слово вже є паліндромом або немає рішення, виведіть -1. В іншому випадку вивести індекс символу, який потрібно видалити.

Формат вхідних даних

Перший рядок містить ціле число \(T\) (\(1 \le T \le 20\)) - кількість тестів.

Потім слідують \(T\) рядків, кожен рядок містить рядок \(S\) (\(1 \le |S| \le 10^5+5\)).

Формат вихідних даних

У вихідний потік для кожного тесту вивести в окремому рядку шуканий індекс або -1.

Приклад вхідних даних

3
aaab
baa
aaa

Приклад вихідних даних

3
0
-1