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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nt=int(input())\nfor _ in range(t):\n    h=input()\n    if len(h)%2:\n        if h[:int(len(h)/2)]==h[int(len(h)/2)+1:][::-1]:\n            print(1)\n        else:\n            print(2)\n    else:\n        if h[:int(len(h)/2)]==h[int(len(h)/2):][::-1]:\n            print(1)\n        else:\n            print(2)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13245