[BOJ 17609] 회문

회문을 확인하는 방법은 word의 양끝에서부터 문자를 확인하면 된다.
만약 일치하지 않는다면
word[s+1:e+1] 또는 word[s:e]이 회문이라면 유사회문이고, 여기서도 회문이 아니라면 회문도, 유사회문도 아니다.
word[a:b]이면 word[b]는 포함되지 않는 것에 유의한다.

isPalindrome(word): word가 회문인지 True/False를 반환. $O(n)$
PalindromeType(word): word가 회문/유사회문/아무것도아닌지 반환. $O(n)$

import sys
#sys.stdin = open('input.txt', 'r')
#sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline

def isPalindrome(word):
    start, end = 0, len(word) - 1
    while start <= end:
        if word[start] != word[end]:
            return False
        start += 1
        end -= 1

    return True

def PalindromeType(word):
    count = 0
    s, e = 0, len(word) - 1
    while s <= e:
        if word[s] == word[e]:
            s += 1
            e -= 1
        else:
            if isPalindrome(word[s + 1:e + 1]) or isPalindrome(word[s:e]):
                count = 1
            else:
                count = 2
            break
    return count


N = int(input())
for _ in range(N):
    word = input().rstrip()
    print(PalindromeType(word))