Minimum Moves to Remove Palindromic Subsequences

You are given T strings. In one move, you can remove a non-empty palindromic subsequence from a string. A subsequence is a sequence that can be derived from the string by deleting some or no elements without changing the order of the remaining elements. Your task is to determine the minimal number of moves required to remove all characters from each string.

It can be proved that for any string composed of lowercase characters, the answer is either \(1\) or \(2\):

• If the string is a palindrome (i.e. it reads the same forwards and backwards, \(s = s^R\)), then you can remove the entire string in one move.
• If the string is not a palindrome, then you can always remove it in two moves.

For example, for the string "ababa", since it is a palindrome, it requires only 1 move. For the string "abcd", which is not a palindrome, it requires 2 moves.

inputFormat

The input is read from standard input and has the following format:

T
s1
s2
...
sT

Where T is an integer representing the number of strings, and each s_i is a non-empty string.

outputFormat

For each test case, output the minimal number of moves required for each string separated by a space. The output should be written to standard output.

Example:

Input:
3
ababa
abcd
aabb
Output:
1 2 2

## sample</p>

1
level

1