Minimum Palindromic Subsequences

You are given a binary string s. A string is called a palindrome if it reads the same forwards and backwards, i.e. if s = s^\mathrm{R}, where s^\mathrm{R} denotes the reverse of s in \(\LaTeX\) format.

Your task is to determine the minimum number of contiguous subsequences the binary string must be divided into so that by reversing each subsequence individually, you can recover the original string.

It can be proven that the answer is 1 if the input string is already a palindrome (i.e. \(s = s^\mathrm{R}\)) and 2 otherwise.

inputFormat

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

outputFormat

For each test case, output a single line containing one integer: the minimum number of contiguous subsequences needed.

## sample

3
101
1100
0110

1
2
1

</p>