Minimum Operations to Empty a String

You are given a string and your task is to determine the minimum number of operations required to make the string empty. In each operation, you can remove a contiguous substring from the string if it is a palindrome.

A palindrome is a string that reads the same forward and backward. For example, the string "ababa" is a palindrome while "abc" is not. It can be proven that any string can be removed in at most two operations: one operation if the entire string is a palindrome, and two operations otherwise.

Your goal is to implement a solution that reads multiple test cases from stdin and outputs the result for each test case to stdout.

The mathematical reasoning can be summarized as:

If \( s = \mathrm{reverse}(s) \) then answer = 1, otherwise answer = 2.

inputFormat

The first line contains an integer \( T \) representing the number of test cases. Each of the following \( T \) lines contains a non-empty string \( s \) consisting of lowercase English letters.

Example:

3
ababa
civic
racecar

outputFormat

For each test case, print a single line containing the minimum number of operations required to make the string empty.

Example:

1
1
1

## sample

3
ababa
civic
racecar

1
1
1

</p>