Goku loves his granddaughter Pan and will do anything to keep her happy.

One day, Pan comes back from school and tells her grandfather about a question which her teacher asked her. She has promised her to give her ice cream if she gives the correct answer to the question. Pan loves ice cream, but she is unable to solve the question, so she asks Goku for help.

The question is :

Given a string, you have to divide the string into minimum possible number of subsequences, such that each subsequence is a palindrome. You need to tell the minimum number of subsequences required to do so.

Goku, being so busy in saving the world against different villains, doesn't know about palindromes, or subsequences. So, he seeks your help.

Input :

First line contains an integer Q, the number of questions.

Each question consists of two lines :

First line contains an integer, l, denoting the length of the string.

Second line contains the string.

Constraints :

1 ≤ Q ≤ 10

1 ≤ l ≤ 10⁵

Characters in the string are from the set {a,b}