You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

Roy loves beautiful strings. A string is considered beautiful if the frequency of peresent character ('a', 'b', or 'c') in the string occurs a prime number of times. For example, if a string has 3 occurrences of 'a', 5 occurrences of 'b', and 7 occurrences of 'c', it is beautiful because 3, 5, and 7 are all prime numbers.
Some beautiful string, "aaaaa", "aabbcc","bbccc","caca", "babacacc" etc.

Roy has a string S consisting of only the characters 'a', 'b', or 'c'. However, the string is not necessarily beautiful. Roy wants to make it beautiful by performing the least number(possibly zero) of operations.
Operations:
In each operation, Roy can change the character at position i (1≤i≤N) in the string
S as follows:

• If the character is 'a', change it to either 'b' or 'c'.
• If the character is 'b', change it to either 'a' or 'c'.
• If the character is 'c', change it to either 'a' or 'b'.

Your task is to determine the minimum number of operations required to make the string beautiful. If it is impossible to make the string beautiful, print -1.

Input

• The first line contains an integer T, (1≤ T ≤100)- the number of test case.
• In each test case following line contains:
• The first line contains an integer N (1≤ N ≤2000)— the length of the string.
• The second line contains the string S of length N, consisting of the characters 'a', 'b', and 'c'.

Output

In each test case, print the minimum number of operations required to make the string beautiful. If it is impossible, print -1.

Sample

4
10
cccacbaaac
10
acbbccaaca
5
bacba
2
ab

1
1
1
1