Harrenhal is the largest castle in the Seven Kingdoms and is the seat of House Whent in the Riverlands, on the north shore of the Gods Eye lake. Since the War of Conquest, however, it has become a dark and ruinous place.
(c) A Wiki of Ice and Fire

Now Harrenhal is too dangerous since it's a nice place for bandits to hide, or even for rebels to start planning overthrowing of the king. So, the current Lord of the Seven Kingdoms has decided, that it's time to completely ruin the castle. For that puposes, he's planning to send some military troops.
In this problem we assume, that Harrenhal can be described as a string H, which consists only of symbols 'a' and 'b'. Harrenhal is completely ruined if and only if the length of H is equal to zero.
So, how to make H empty? Send a military troop! When a military troop of the king reach the castle, they delete some palindromic subsequence S of H. For example, let H = 'abbabaab'. Then the current military troop can choose S = 'ababa'(Let's make symbols of S bold in H: 'abbabaab'). After deleting S, H will be equal to 'bab'. Military troops are free to choose any possible palindromic subsequence of H.
Your task is pretty simple: determine the minimal number of military troops, that the Lord of the Seven Kingdoms has to send in order to ruin Harrenhal.

-----Note-----

Maybe, some of you aren't familiar with definitions from the statement. Here're some articles that could help you to understand the problem correctly:

- Subsequence: http://en.wikipedia.org/wiki/Subsequence
- Palindrome: http://en.wikipedia.org/wiki/Palindrome

-----Input-----
The first line of the input contains an integer T, denoting the number of test cases.
The next T lines contain a string H each, denoting the string, that describes the current state of Harrenhal for the corresponding test cases.
It's guaranteed, that each H consists only of symbols 'a' and 'b'.

-----Output-----
The output should contain exactly T lines. i'th line of the output should contain the only integer: the minimal number of military troops, that the Lord of the Seven Kingdoms has to send in order to ruin Harrenhal for the corresponding test cases.

-----Constraints-----
- 1 ≤ |H| ≤ 100000, for each H.
- Subtask 1(30 points): each H in the input is a palindrome, 1 ≤ T ≤ 6;
- Subtask 2(70 points): 1 ≤ T ≤ 9.

-----Example-----
Input:
1
abbabaab

Output:
2

-----Explanation-----
There're multiple ways to ruin Harrenhal in the example test. Let's consider one of them.
The first troop can delete S = 'ababa'('abbabaab'). After that, H = 'bab'.
The second troop can delete S = 'bab'('bab'). After that, H is empty and that's it.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
for _ in range(int(input())):
    g=input()
    h=g[::-1]
    if h==g :
        print(1)
    else:
        print(2)
    

# cook your dish here
for _ in range(int(input())):
    string = input()
    if string == string[::-1]:
        print('1')
    else:
        print('2')
    

def isPalindrome(S,N):
    for i in range(N):
        if(S[i]!=S[N-1-i]):
            return False
    return True

T = int(input())
ans = []

for _ in range(T):
    S = input()
    N = len(S)

    if(isPalindrome(S,N)):
        ans.append(1)
    else:
        ans.append(2)

for i in ans:
    print(i)


# cook your dish here
def palin(arr):
    for i in range(len(arr)//2):
        if arr[i]!=arr[len(arr)-1-i]:
            return -1
    return 1
t=int(input())
for _ in range(t):
    arr=input()
    if palin(arr)==1:
        print(1)
    else:
        print(2)
        

# cook your dish here
for _ in range(int(input())):
    s=input()
    n=len(s)
    ans=len(set(s))
    if ans==1:
        print(1)
        
    else:
        a,b,f=0,-1,0
        for i in range(n//2):
            if s[a]!=s[b]:
                print(ans)
                f=1 
                break
            
            else:
                a+=1 
                b-=1
            
        if f==0:
            print(1)

# cook your dish here
for _ in range(int(input())):
    s=input()
    n=len(s)
    ans=len(set(s))
    if ans==1:
        print(1)
        
    else:
        a,b,f=0,-1,0
        for i in range(n//2):
            if s[a]!=s[b]:
                a+=1 
                b-=1
                print(ans)
                f=1 
                break
            
        if f==0:
            print(1)

# cook your dish here
for _ in range(int(input())):
    s=input()
    n=len(s)
    ans=len(set(s))
    if ans==1:
        print(1)
        
    else:
        a,b,f=0,-1,0
        for i in range(n//2):
            if s[a]!=s[b]:
                print(ans)
                f=1 
                break
            
        if f==0:
            print(1)

t=int(input())
for i in range(t):
    h=input()
    hr=h[::-1]
    if h==hr:
        print(1)
    else:
        print(2)
    


t=int(input())
while(t):
    s=input()
    if s==s[::-1]:
        print(1)
    else:
        print(2)
    t=t-1       

# cook your dish here
t=int(input())
for _ in range(t):
    h=input()
    if h == h[::-1]:
        print(1)
    else: print(2)

# cook your dish here
t=int(input())
for _ in range(t):
    h=input()
    if len(h)%2:
        if h[:int(len(h)/2)]==h[int(len(h)/2)+1:][::-1]:
            print(1)
        else:
            print(2)
    else:
        if h[:int(len(h)/2)]==h[int(len(h)/2):][::-1]:
            print(1)
        else:
            print(2)

# cook your dish here
t=int(input())
while t:
    h=input()
    if len(h)%2:
        if h[:int(len(h)/2)]==h[int(len(h)/2)+1:][::-1]:
            print(1)
        else:
            print(2)
    else:
        if h[:int(len(h)/2)]==h[int(len(h)/2):][::-1]:
            print(1)
        else:
            print(2)
    t-=1

t=int(input())
while(t>0):
    q=0
    a=input()
    n=len(a)
    for i in range(n//2):
        if(a[i]!=a[n-i-1]):
            q=1
            print(2)
            break
    if(q==0):
        print(1)
    t-=1

from collections import defaultdict
import math
for _ in range(int(input())):
    s=input()
    if s==s[::-1]:
        print(1)
    else:
        print(2)

# cook your dish here
def isPalindrome(s):
    return(s==s[::-1])
t=int(input())
for i in range(t):
    word=input()
    if(isPalindrome(word)):
        print(1)
    else:
        print(2)



# cook your dish here
def isPalindrome(s):
    return(s==s[::-1])
t=int(input())
for i in range(t):
    word=input()
    if(isPalindrome(word)):
        print(1)
    else:
        print(2)



# cook your dish here
test=int(input())
for _ in range(test):
    n=input()
    i=t=0
    l=len(n)
    if l==0:
        continue
    j=l-1
    while i<l//2:
        if n[i]!=n[j]:
            t=1
            break
        i+=1
        j-=1
    if t==0:
        print(1)
    else:
        print(2)

for i in range(int(input())):
    a=input()
    i=t=0
    l=len(a)
    if l==0:
        continue
    j=l-1
    while i<l//2:
        if a[i]!=a[j]:
            t=1
            break
        i+=1
        j-=1
    if t==0:
        print(1)
    else:
        print(2)

for _ in range(int(input())):
	H=list(input())
	v=1
	if H!=H[::-1]:
		v+=1
	print(v)
		

T = int(input())
for i in range(T):
    N = input()
    s = list(N)
    t = s[::-1]
    if t == s:
        print(1)
    else:
        print(2)

for j in range(int(input())):
    x=input()
    a=list(x)
    z=a[::-1]
    if(z==a):
        print(1)
    else:
        print(2)

# cook your dish here
"""
This is a tricky problem

as we can remove some substrings and there are only two characters the maximum
possible answer is 2
1. Remove all a
2. Remove all b

"""


def is_palindrome(s):
    result = True
    for i in range(len(s)):
        if s[i] != s[len(s) - 1 - i]:
            return False
    return True

testcase = int(input())
for z in range(testcase):
    s = input()
    if (is_palindrome(s)):
        print(1)

    else:
        print(2)


for _ in range(int(input())):
    s = str(input())
    i = 0
    j = len(s)-1
    f = 0
    while(i<j):
        if s[i]!=s[j]:
            f= 1
            break
        i+=1
        j-=1
    if f==1:
        print(2)
    else:
        print(1)

for _ in range(int(input())):
    s = str(input())
    i = 0
    j = len(s)-1
    f = 0
    while(i<j):
        if s[i]!=s[j]:
            f= 1
            break
        i+=1
        j-=1
    if f==1:
        print(2)
    else:
        print(1)

for i in range(int(input())):
    a=input()
    b=a[::-1]
    if a==b:
        print(1)
    else:
        print(2)