Let $c$ be the number of positions $i$ such that $s_i \ne s_{i+1}$.

If $c=0$, all characters are equal. The whole string is always a palindrome, so we can repeatedly delete characters until only one remains.

If $c=1$, the string consists of exactly two contiguous blocks of equal characters. Any palindrome of length at least $2$ must be contained entirely inside one of these blocks, so every operation only shortens a block and can never remove it completely. Therefore, both blocks remain nonempty, and the minimum possible length is $2$.

If $c\ge 2$, then the string has at least three blocks. First, we can shrink every block to length $1$, because any block of equal characters is itself a palindrome of length at least $2$ as long as its length is at least $2$. So we may assume the string becomes alternating.

Now consider an alternating string of length at least $3$. Its last three characters are always of the form $010$ or $101$; hence, they form a palindrome. Deleting the last character of this palindrome shortens the string by $1$, and the remaining string is still alternating. Repeating this step, we can reduce the string to length $3$. Then the whole string is a palindrome, and deleting its middle character gives two equal characters, which can be reduced to length $1$ in one more move.

Hence, the answer is $2$ iff $c=1$, and $1$ otherwise.

Time Complexity: $\mathcal{O}(n)$.

设 $c$ 为满足 $s_i \ne s_{i+1}$ 的位置 $i$ 的数量。

若 $c=0$，则所有字符均相同。整个字符串始终是回文串，因此我们可以反复删除字符，直到只剩一个字符为止。

若 $c=1$，则字符串恰好由两个连续的相同字符块组成。任何长度至少为 $2$ 的回文串必须完全包含在其中一个块内，因此每次操作只会缩短一个块，而永远无法将其完全移除。因此，两个块均保持非空，最小可能长度为 $2$。

若 $c\ge 2$，则字符串至少有三个块。首先，我们可以将每个块缩短至长度为 $1$，因为任何长度至少为 $2$ 的相同字符块本身就是一个长度至少为 $2$ 的回文串。因此，我们可以假设字符串变为交替形式。

现在考虑一个长度至少为 $3$ 的交替字符串。它的最后三个字符总是形如 $010$ 或 $101$，因此它们构成一个回文。删除这个回文的最后一个字符会使字符串长度减少 $1$，而剩余的字符串仍然是交替的。重复这一步骤，我们可以将字符串缩减到长度为 $3$。此时整个字符串是一个回文，删除其中间字符会得到两个相同的字符，再经过一次操作即可缩减到长度为 $1$。

因此，当且仅当 $c=1$ 时答案为 $2$，否则答案为 $1$。

时间复杂度：$\mathcal{O}(n)$。

Solution

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
        int n;
        string s;
        cin >> n >> s;
 
        int count = 0;
        for(int i = 0; i < n - 1; i++) if(s[i] != s[i + 1]) count++;
 
        cout << (count == 1 ? 2 : 1) << '\n';
    }
 
    return 0;
}