Minimum Operations to Form a Palindrome

You are given a string s of length n. You are allowed to perform the following operation: choose an index i (where 0 ≤ i < n-1), then split the string into two non-empty parts a and b such that s = a + b, and form a new string s' = b + a.

The goal is to determine the minimum number of operations required to transform s into a palindrome. Formally, you need to find the minimum k (with 0 ≤ k ≤ 2) such that applying the operation k times results in a string that is a palindrome. Recall that a string is a palindrome if it reads the same forward and backward, i.e. if \( s = s^R \), where \( s^R \) denotes the reverse of \( s \).

It can be shown that if the string is not already a palindrome, at most 2 operations are needed.

inputFormat

The input is given via stdin and consists of:

• An integer t on the first line, representing the number of test cases.
• Then t lines follow, each containing a non-empty string s.

It is guaranteed that each string contains only lowercase English letters.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of operations needed to transform the string into a palindrome.

The output should be written to stdout.

## sample

3
aba
abc
a

0
2
0

</p>