The new queen of Zing Dynasty is The Queen K oliliKo .
She is very fond of her name.
She orders everyone in Zing to present her a KOLILIKO string.
A string is called KOLILIKO string if it follows the following conditions-
• It can be sliced into exactly four parts of equal length. ( KO LI LI KO )
• The first part is identical to the last part.
• The second part is identical to the third part.
Little Fuji also has a string and wants to present it to Queen but he doesn’t know whether it’s a KOLILIKO string or not.
Help Fuji to present his string to the queen at a minimum cost.
Following are rules/costs to manipulate any string in Zing:-
• Characters of any particular part can be shuffled within that part without any cost.
• Characters cannot be transferred from one part to another.
• Replacing any character of the string with a new one costs 1 Unit .
The first line of input contains a positive integer Q denoting the number of Queries.
The first line of each query contains a positive integer L denoting the length of the string.
The next line of the query contains a string of length L.
Print “YES” (without quotes) if there is no cost to convert the string to KOLILIKO String.
Else print “NO” (without quotes) followed by an integer denoting the minimum cost.
(L is always a multiple of 4)
String only consists of lower case letters of the english alphabets.
Sum of L over all queries ≤1000000
2 4 abcd 8 abcdcdab
NO 2 YES
The first string is obviously not a KOLILIKO String. The minimum cost to convert it into KOLILIKO String is 2. One of the ways is to change c to b and d to a . The resulting String will be abba.
The second string is already a KOLILIKO String.