Minimum Operations to Remove Palindromic Subsequences

You are given an integer T and T strings. For each string s, you need to determine the minimum number of operations required to make the string empty by removing palindromic subsequences.

In one operation, you can remove any subsequence from the string if it forms a palindrome. It can be proven that the answer for any string is always either 1 or 2:

• If the string is already a palindrome (i.e. s = s^R where s^R denotes the reverse of s), then you can remove the entire string in one operation.
• If the string is not a palindrome, then you can remove all occurrences of one character in the first operation and the remaining characters in the second operation.

Note: The empty string is considered a palindrome.

inputFormat

The first line contains an integer T indicating the number of test cases. Each of the following T lines contains a non-empty string s.

Example:

3
abb
abccba
abcd

outputFormat

For each test string, output the minimum number of operations required to remove all characters from the string. Print each answer on a separate line.

Example:

2
1
2

## sample

1
a

1

</p>