Minimum Palindromic Substring Partition

Given a binary string, determine the minimum number of substrings into which the string can be partitioned so that every substring is a palindrome. A palindrome is a string that reads the same forwards and backwards. It can be proven that for any binary string, the answer is either (1) (if the string itself is a palindrome) or (2) (if it is not).

For example, for the string 11011, since it reads the same backwards, the answer is (1). For the string 00010, which is not a palindrome, the answer is (2).

inputFormat

The first line of input contains an integer (T) representing the number of test cases. Each of the following (T) lines contains a binary string (s).

outputFormat

For each test case, output a single line containing the minimum number of palindromic substrings into which (s) can be partitioned. Output (1) if the string is a palindrome, otherwise output (2).## sample

1
11011

1