There are four popular football teams in the region of Sao Paulo: Corinthians, Palmeiras, Santos and Sao Paulo. Exactly n players among those football teams were pre-selected for an award regarding their performance on the championship.

Today is the big day when one of them will be awarded as the ultimate champion. The players have now arrived, and everyone remembered their seats row (which is the same for all the n players) but not their column number. And now, as one of the most basic and known rules about football ceremonies had been violated, you’re in a hurry to satisfy the rule by switching as few players as possible.

This rule, which I guess you should be familiar with but we are going to state it for the sake of completeness, states that there cannot be 3 or more players from the same team sitting in consecutive seats.

Input

You’ll first be given an integer T, which represents the total number of test cases. Each test case consist of a single integer N (1<= N <= 20) that represents the number of players invited to the ceremony. This is followed by a string S of length N representing the team at which each player belongs to. Each character S[i] of S will be one of the following C, P, N, S, meaning that the player seated at position i belongs to Corinthians, Palmeiras, Santos or Sao Paulo respectively.

Each test case will be separated by a blank line.

Output

The output should consist of a single number per test case. That number should be the minimum number of players that need to change their seats to satisfy the rule, if there is no way to satisfy the rule output -1 instead.

Example

Input:
2
8
CCCCCCPN

3
CCC

Output:
4
-1