Настер і паліндромічні зрушення

Вхідні дані

Перший рядок містить одне ціле число $t$ (1 \le t \le 10^4) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить одне ціле число $n$ (1 \le n \le 4 \cdot 10^5) — довжина рядка.

Другий рядок містить рядок $s$ довжиною $n$, що складається з малих англійських літер.

Гарантується, що сума всіх $n$ у всіх тестових випадках не перевищує 4 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — мінімальну кількість зрушень, потрібну для того, щоб рядок став паліндромом, або $-1$, якщо це неможливо.

Приклади

Примітка

У першому тестовому випадку, n=5, s=\text{``ababa''}

• Рядок вже є паліндромом: $\text{ababa}$ однаково читається зліва направо і справа наліво.

• Зрушення не потрібні.

• Відповідь: $0$

У третьому тестовому випадку, n=7, s=\text{``abbaccc''}

• Оригінал: $\text{abbaccc}$ (не паліндром)

• Після $1$ зрушення вліво: $\text{bbaccca}$ (не паліндром)

• Після $2$ зрушень вліво: $\text{bacccab}$ (паліндром: $\text{bacccab}$)

• Перевірка: $\text{bacccab}$ однаково читається зліва направо і справа наліво.

• Мінімально потрібно $2$ зрушення.

• Відповідь: $2$

Оцінювання

1. Подзадача $1$ ($10$ очок) : (1 \le \sum n \le 100)

2. Подзадача $1$ ($20$ очок) : (1 \le \sum n \le 5000)

3. Подзадача $3$ ($70$ очок) : (1 \le \sum n \le 5 \cdot 10^4)

4. Подзадача $4$ ($150$ очок) : Без додаткових обмежень.