Minimum Operations to Empty a String by Removing Palindromic Substrings

You are given a non-empty string s. In one operation, you can remove any palindromic substring from s. The goal is to remove all characters of the string using the minimum number of such operations. It can be proven that the answer is always either 1 or 2. In particular, if the string is a palindrome, you can remove it in one go, otherwise you will need 2 operations.

For example, if s = "ababa", the string is a palindrome and the answer is 1. If s = "abc", the answer is 2 since the entire string is not a palindrome.

Note: A single character is always a palindrome.

inputFormat

The input is given via standard input with the following format:

T
s1
s2
...
sT

Here, T (1 ≤ T ≤ 10⁵) is the number of test cases, and each of the following si is a non-empty string consisting of lowercase English letters. It is guaranteed that the total length of all strings does not exceed 10⁶.

outputFormat

For each test case, output the minimum number of operations needed to make the string empty by removing palindromic substrings. Each answer should be printed on a separate line to standard output.

## sample

1
ababa

1

</p>