Minimum Palindromic Length

You are given a string s. You are allowed to perform the following two operations any number of times:

1. Reverse any substring of s.
2. Delete the first character of s.

Your goal is to obtain a palindrome with the minimum possible length. Notice that if s is already a palindrome then the answer is the length of s; otherwise, by deleting characters you can always reduce the string to a single character (which is trivially a palindrome).

In mathematical terms, if s is a palindrome then \(ans = |s|\), otherwise \(ans = 1\).

inputFormat

The first line of input contains an integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains a non-empty string \(s\) to be processed.

outputFormat

For each test case, print one integer on a separate line representing the minimum length of a palindrome that can be obtained.

## sample

1
a

1

</p>