[String] 17609번 - 회문(38일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline

# 유사회문 판단 함수
def pseudo(a, left, right):
    while left < right:
        if a[left] == a[right]:
            left += 1
            right -= 1
        else:
            return False
    return True

# 회문 판단 함수
def palindrome(a, left, right):
    while left < right:
        #주어진 문자열이 회문인지 탐색
        if a[left] == a[right]:
            left += 1
            right -= 1
        #아닐 경우, 좌우로 한 칸씩 줄여서 다시 회문 탐색
        else:
            res1 = pseudo(a, left+1, right)
            res2 = pseudo(a, left, right-1)
            #한칸 이동으로 회문이 가능한 경우 유사 회문
            if res1 == True or res2 == True:
                return 1
            #한칸 이동으로 회문이 안되는 경우
            else:
                return 2
    return 0

n = int(input())

for _ in range(n):
    string = input().rstrip()
    #입력받은 문자열로 회문 탐색 시작
    res = palindrome(string, 0, len(string)-1)
    print(res)