Nasser and Palindromic Shifts

Input

The first line contains a single integer $t$ (1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains a single integer $n$ (1 \le n \le 4 \cdot 10^5) — the length of the string.

The second line contains a string $s$ of length $n$ consisting of lowercase English letters.

It is guaranteed that the sum of all $n$ over all test cases does not exceed 4 \cdot 10^5.

Output

For each test case, print a single integer — the minimum number of shifts needed to make the string a palindrome, or $-1$ if it's impossible.

Examples

Note

In the first test case, n=5, s=\text{``ababa''}

• The string is already a palindrome: $\text{ababa}$ reads the same forward and backward.

• No shifts are needed.

• Answer: $0$

In the third test case, n=7, s=\text{``abbaccc''}

• Original: $\text{abbaccc}$ (not palindrome)

• After $1$ left shift: $\text{bbaccca}$ (not palindrome)

• After $2$ left shifts: $\text{bacccab}$ (palindrome: $\text{bacccab}$)

• Check: $\text{bacccab}$ reads the same forward and backward.

• Answer: $2$

Scoring

1. Subtask $1$ ($10$ points) : (1 \le \sum n \le 100)

2. Subtask $1$ ($20$ points) : (1 \le \sum n \le 5000)

3. Subtask $3$ ($70$ points) : (1 \le \sum n \le 5 \cdot 10^4)

4. Subtask $4$ ($150$ points) : No additional constraints.