Palindrome

Interview

Time limit1sMemory limit512 MB

Summary

For each string, print 0 if it is a palindrome, 1 if deleting one character makes it a palindrome, or 2 otherwise.

Level: Medium5 of 10
Topics: String, Two pointers, Greedy, Implementation
Solved: No attempts yet

Problem

A palindrome is a string whose characters read in the same order from front to back and from back to front. For example, ‘abba’, ‘kayak’, ‘reviver’, and ‘madam’ are all palindromes. If a string is not a palindrome itself but can be turned into one by deleting a single character, we call it a “pseudo palindrome”. For example, ‘summuus’ is a pseudo palindrome because deleting the 5th or 6th character ‘u’ gives ‘summus’, a palindrome.

For each given string, determine whether it is a palindrome itself, a pseudo palindrome that becomes a palindrome after deleting one character, or neither. Output 0 if the string is a palindrome, 1 if it is a pseudo palindrome, and 2 otherwise.

Input

The first line of input contains an integer $T(1 \le T \le 30)$ , the number of strings. The next $T$ lines each contain one string. The length of each string is between 3 and 100,000, and it consists only of lowercase English letters.

Output

For each string, decide whether it is a palindrome, a pseudo palindrome, or neither, and print 0, 1, or 2 on its own line in that order.

Examples1

Example 1

Input

7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc

Expected output