Nasser və Palindromik Keçidlər

Giriş

İlk sətir tək tam ədəd olan $t$ (1 \le t \le 10^4) — test halları sayı.

Hər test halının ilk sətiri tək tam ədəd olan $n$ (1 \le n \le 4 \cdot 10^5) — sətirin uzunluğu.

İkinci sətir kiçik ingilis hərflərindən ibarət $n$ uzunluq sətiri $s$ ehtiva edir.

Bütün test hallarının $n$ cəmində toplam sayı 4 \cdot 10^5 keçməyəcəyi təmin edilir.

Çıxış

Hər test halı üçün sətiri palindrom etmək üçün lazım olan minimal keçid sayını, əgər mümkün deyilsə $-1$ çap edin.

Nümunələr

Qeyd

Birinci test halında, n=5, s=\text{``ababa''}

• Sətir artıq palindromdur: $\text{ababa}$ əvvəl və geri oxunuşda eyni.

• Heç bir keçid lazım deyil.

• Cavab: $0$

Üçüncü test halında, n=7, s=\text{``abbaccc''}

• Orijinal: $\text{abbaccc}$ (palindrom deyil)

• $1$ sol keçiddən sonra: $\text{bbaccca}$ (palindrom deyil)

• $2$ sol keçiddən sonra: $\text{bacccab}$ (palindrom: $\text{bacccab}$)

• Yoxla: $\text{bacccab}$ əvvəl və geri oxunuşda eyni.

• Minimum $2$ keçid.

• Cavab: $2$

Bal hesablama

1. Alt problem $1$ ($10$ xal) : (1 \le \sum n \le 100)

2. Alt problem $1$ ($20$ xal) : (1 \le \sum n \le 5000)

3. Alt problem $3$ ($70$ xal) : (1 \le \sum n \le 5 \cdot 10^4)

4. Alt problem $4$ ($150$ xal) : Əlavə məhdudiyyət yoxdur.