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: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
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 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)


tc = int(input())
for _ in range(tc):
	string = input()
	if string == string[::-1]:
		print(1)
	else:
		print(2)


def palindrome(s):
	for i in range(0, len(s) // 2):
		if s[i] != s[-i - 1]:
			return True
	return False
t = int(input())
for _ in range(0, t):
	s = input()
	if palindrome(s):
		print(2)
	else:
		print(1)


for _ in range(int(input())):
	s = input().strip()
	if 'a' not in s or 'b' not in s or s == s[::-1]:
		print(1)
	else:
		print(2)


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


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)


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)


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)
	elif h[:int(len(h) / 2)] == h[int(len(h) / 2):][::-1]:
		print(1)
	else:
		print(2)
	t -= 1


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


def Solve(s):
	return 1 if s == s[::-1] else 2
for _ in range(int(input())):
	s = input()
	print(Solve(s))


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)


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


tests = int(input())
for i in range(tests):
	string = input()
	is_palindrome = True
	y = len(string) - 1
	x = 0
	while x < y:
		if string[x] != string[y]:
			is_palindrome = False
			break
		x += 1
		y -= 1
	if is_palindrome:
		print(1)
	else:
		print(2)


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


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


for t in range(int(input())):
	h = input()
	pal = 0
	for i in range(len(h) // 2):
		if h[i] == h[len(h) - i - 1]:
			pass
		else:
			pal = 1
	if pal == 0:
		print(1)
	else:
		print(2)


T = int(input())
for t in range(T):
	H = input()
	if H[::-1] == H:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	s = input()
	print(1 if s == s[::-1] else 2)


def palindrome(s):
	for i in range(len(s)):
		if s[i] == s[l - i - 1]:
			result = True
		else:
			result = False
			break
	return result
n = int(input())
while n > 0:
	s = input()
	l = len(s)
	if palindrome(s) == True:
		print('1')
	else:
		print('2')
	n -= 1


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


for _ in range(int(input())):
	s = input()
	p = len(s)
	count = 0
	t = 0
	for i in range(p // 2 - 1):
		if s[i] != s[-1 - i]:
			t = 1
			break
	if t:
		print(2)
	else:
		print(1)


for _ in range(int(input())):
	string = input()
	ans = 1
	if string != string[::-1]:
		ans = 2
	print(ans)


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


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


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)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	H = insr()
	ans.append(1 if H == H[::-1] else 2)
outplt(ans)


for _ in range(int(input())):
	g = input()
	h = g[::-1]
	if h == g:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	x = input()
	if x == x[::-1]:
		print('1')
	else:
		print('2')


def check(string):
	result = 1
	N = len(string)
	for i in range(N):
		if string[i] != string[N - 1 - i]:
			result = 2
			break
	return result
for _ in range(int(input())):
	H = input()
	print(check(H))


T = int(input())
for _ in range(T):
	N = input()
	if N == N[::-1]:
		print(1)
	else:
		print(2)


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 _ in range(int(input())):
	H = input()
	n = len(H)
	l1 = n // 2 - 1
	if n % 2 == 0:
		l2 = n // 2
		count = 0
	else:
		l2 = n // 2 + 1
		count = 1
	i = 0
	j = n - 1
	while True:
		if i > l1 and j < l2:
			break
		if H[i] == H[j]:
			count += 2
		i += 1
		j -= 1
	if count == n:
		print('1')
	else:
		print('2')


T = int(input())
for j in range(0, T):
	a = input()
	a = list(a)
	b = len(a)
	for j in range(0, b // 2):
		if a[j] != a[b - j - 1]:
			print(2)
			break
	else:
		print(1)


for i in range(int(input())):
	a = list(input())
	n = len(a)
	m = 0
	for j in range(n // 2):
		if a[j] != a[n - j - 1]:
			print('2')
			m = 1
			break
	if m == 0:
		print('1')


for _ in range(int(input())):
	h = input()
	(l, f) = (len(h), 0)
	for i in range(l):
		if h[i] != h[l - 1 - i]:
			f = 1
			break
	if f:
		print('2')
	else:
		print('1')


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)


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)
	elif h[:int(len(h) / 2)] == h[int(len(h) / 2):][::-1]:
		print(1)
	else:
		print(2)


T = int(input())
respuestas = list()
for x in range(T):
	H = input()
	for x in range(len(H) // 2):
		if H[x] != H[len(H) - x - 1]:
			print(2)
			break
	else:
		print(1)


def is_palindrome(s1):
	n = len(s1)
	for i in range(n // 2):
		if s1[i] != s1[n - i - 1]:
			return False
	return True
for _ in range(int(input())):
	s1 = input()
	if is_palindrome(s1):
		print(1)
	else:
		print(2)


from math import gcd, sqrt, ceil, floor, log10
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
sys.setrecursionlimit(3000000)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))

def solve(*args, **kwargs):
	h = args[0]
	return 2 if h != h[::-1] else 1

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg2 = inp(str)
		res = solve(*(arg2,))
		if type(res) in {list, tuple, set}:
			print(*res, sep=' ')
		else:
			print(res)
main()


for _ in range(int(input())):
	h = str(input())
	flag = 0
	for i in range(len(h) // 2):
		if h[i] != h[len(h) - i - 1]:
			flag = 1
			print(2)
			break
	if flag == 0:
		print(1)


for _ in range(int(input())):
	s = input()
	n = len(s)
	mid = n // 2
	flag = False
	for i in range(mid):
		if s[i] != s[n - i - 1]:
			flag = True
			break
	if flag:
		print(2)
	else:
		print(1)


def pal(s):
	s1 = s[::-1]
	if s == s1:
		return True
for _ in range(int(input())):
	H = input()
	if pal(H):
		print(1)
	else:
		print(2)


from collections import Counter
for _ in range(int(input())):
	h = input()
	for i in range(len(h) // 2):
		if h[i] != h[len(h) - i - 1]:
			break
	else:
		print(1)
		continue
	h1 = dict(Counter(h))
	print(len(list(h1.keys())))


def isPalindrome(s):
	li = len(s) - 1
	for i in range(len(s) // 2):
		if s[i] != s[li - i]:
			return False
	return True
T = int(input())
for _ in range(T):
	H = input()
	if isPalindrome(H):
		print(1)
	else:
		print(2)


def hhal(s):
	n = len(s)
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			return 2
	return 1
t = int(input())
for _ in range(t):
	s = input()
	print(hhal(s))


def isPalin(s, n):
	l = 0
	r = n - 1
	while l < r:
		if s[l] != s[r]:
			return False
		l += 1
		r -= 1
	return True
for _ in range(int(input())):
	h = input()
	n = len(h)
	if isPalin(h, n):
		print(1)
	else:
		print(2)


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


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 _ in range(int(input())):
	H = input()
	if H[::-1] == H:
		print(1)
	else:
		print(2)


t = int(input())
for u in range(t):
	a = input()
	n = True
	for i in range(len(a) // 2):
		if a[i] != a[-i - 1]:
			n = False
			break
	if n:
		print(1)
	else:
		print(2)


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


t = int(input())
for _ in range(t):
	h = input()
	z = len(h)
	for i in range(z // 2 - 1):
		if h[i] != h[z - i - 1]:
			print(2)
			break
	else:
		print(1)


case = int(input())
for i in range(case):
	s = input()
	n = len(s) // 2
	t = 1
	for i in range(n):
		if s[i] != s[-i - 1]:
			t = 0
			break
		else:
			t = 1
	if t == 1:
		print(1)
	else:
		print(2)