Minimum Operations to Empty a String

You are given an integer \(n\) and a string \(s\) of length \(n\). In one operation, you can remove all characters from \(s\) if \(s\) is a palindrome. Otherwise, your only option is to remove one character at a time.

Your task is to compute the minimum number of operations required to empty the string.

Formally, let \(s\) be a string. The minimum number of operations \(f(s)\) is defined as:

[ f(s) = \begin{cases} 1, & \text{if } s = s^R \ n, & \text{otherwise} \end{cases} ]

Here, \(s^R\) denotes the reverse of the string \(s\), and \(n\) is the length of the string.

Examples:

• For \(n = 3\) and \(s = \texttt{abc}\), since "abc" is not a palindrome, the answer is 3.
• For \(n = 4\) and \(s = \texttt{abba}\), since "abba" is a palindrome, the answer is 1.
• For \(n = 2\) and \(s = \texttt{aa}\), the answer is 1.

inputFormat

The first line contains a single integer \(T\) denoting the number of test cases.

Each test case consists of one line containing an integer \(n\) and a string \(s\) (separated by space), where \(n\) is the length of \(s\).

You may assume that the string \(s\) does not contain any spaces.

outputFormat

For each test case, print the minimum number of operations required to empty the string on a separate line.

## sample

3
3 abc
4 abba
2 aa

3
1
1

</p>