Сізге ұзындығы \(n\) болатын, тек кіші ағылшын әріптерінен тұратын \(s\) жолы берілген.

Бос емес \(t\) жолын қарастырайық. Символ \(c\) жол \(t\) ішінде доминант деп аталады, егер \(c\) символы \(t\) жолында кез келген басқа кіші ағылшын әрпінен қатаң түрде көп кездессе.

Бос емес \(t\) жолы теңгерілген деп аталады, егер \(t\) жолында доминант символ бар болса.

Бір операцияда екі позицияны \(i\) және \(j\) \((1 \le i, j \le n)\) таңдап, \(s_i\) және \(s_j\) символдарын орындарымен ауыстыруға болады.

Бірнеше операция орындап, алынған жолдың әрбір бос емес префиксі теңгерілген болатындай ету керек.

Минималды мүмкін операциялар санын табыңыз. Егер бұл мүмкін болмаса, \(-1\) шығарыңыз.

Енгізу

Бірінші жолда бір бүтін сан \(T\) \((1 \le T \le 2 \cdot 10^5)\) — тесттер саны беріледі.

Әр тест екі жолдан тұрады.

Әр тесттің бірінші жолында бір бүтін сан \(n\) \((1 \le n \le 2 \cdot 10^5)\) — жолдың ұзындығы беріледі.

Әр тесттің екінші жолында бір жол \(s\) — берілген жол беріледі.

\(s\) жолының ұзындығы \(n\) және ол тек кіші ағылшын әріптерінен тұрады.

Барлық тесттер бойынша \(n\) қосындысы \(2 \cdot 10^5\)-тен аспайтынына кепілдік беріледі.

Шығару

Әр тест үшін бір бүтін сан шығарыңыз — минималды мүмкін операциялар саны, немесе талапты орындау мүмкін болмаса, \(-1\).

Мысалдар

Енгізу 1

5
4
abcc
5
aaabb
4
aabb
1
z
6
abcaaa

Жауап 1

2
0
-1
0
1