Given a string consisting of the letters $\textbf{a}$, $\textbf{b}$ and $\textbf{c}$, we can perform the following operation: 

Take any two adjacent distinct characters and replace them with the third character. 

Find the shortest string obtainable through applying this operation repeatedly.  

For example, given the string $\textbf{aba}$ we can reduce it to a $\mbox{1}$ character string by replacing $\textbf{ab}$ with $\textbf{c}$ and $\textbf{ca}$ with $\mbox{b}$: $\textbf{aba}\to\textbf{ca}\to\textbf{b}$.  

Function Description  

Complete the stringReduction function in the editor below.  It must return an integer that denotes the length of the shortest string obtainable.  

stringReduction has the following parameter: 

- s: a string  

Input Format

The first line contains the number of test cases $\boldsymbol{\boldsymbol{t}}$.  

Each of the next $\boldsymbol{\boldsymbol{t}}$ lines contains a string $\boldsymbol{\mathrm{~S~}}$ to process.

Constraints

$1\leq t\leq100$
$1<|s|\leq100$

Output Format

For each test case, print the length of the resultant minimal string on a new line.  

Sample Input
3  
cab  
bcab  
ccccc

Sample Output
2  
1  
5

Explanation

For the first case, there are two solutions:  $\textbf{cab}\to\textbf{cc}$ or $\textbf{cab}\to\textbf{bb}$. 

For the second case, one optimal solution is: $\textbf{bcab}\to\textbf{aab}\to\textbf{ac}\to\textbf{b}$. 

For the third case, no operations can be performed so the answer is $5$.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import collections, sys
char_set = 'abc'
T = int(sys.stdin.readline())
for i in range(T):
	chars = sys.stdin.readline().lower().strip()
	count = collections.Counter(chars)
	parities = [v % 2 for v in count.values()]
	while len(parities) < len(char_set):
		parities.append(0)
	if len(count.values()) == 1:
		print(len(chars))
	elif len(set(parities)) == 1:
		print(2)
	else:
		print(1)


__author__ = 'jonghewk'

def reductions(string):
	d = [0, 0, 0]
	for letter in string:
		if letter == 'a':
			d[0] += 1
		elif letter == 'b':
			d[1] += 1
		else:
			d[2] += 1
	while True:
		count = 0
		for i in d:
			if i == 0:
				count += 1
		if count >= 2:
			break
		d.sort(reverse=True)
		d[0] += -1
		d[1] += -1
		d[2] += 1
	sum = 0
	for i in d:
		sum += i
	print(sum)
T = int(input())
cases = []
for i in range(T):
	cases.append(input().strip())
for w in cases:
	reductions(w)


def stringReduction(string):
	a = string.count('a')
	b = string.count('b')
	c = string.count('c')
	if [a, b, c].count(0) >= 2:
		return a + b + c
	elif all((v % 2 == 0 for v in [a, b, c])) or all((v % 2 == 1 for v in [a, b, c])):
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def countReduction(s):
	(a, b, c) = (0, 0, 0)
	for s_ in s:
		if s_ == 'a':
			a += 1
		if s_ == 'b':
			b += 1
		if s_ == 'c':
			c += 1
	if a == 0 and b == 0 or (b == 0 and c == 0) or (c == 0 and a == 0):
		return a + b + c
	if a % 2 == b % 2 == c % 2:
		return 2
	return 1
T = int(input())
for t in range(0, T):
	s = input()
	print(countReduction(s))


from collections import Counter

def main():
	t = int(input())
	for _ in range(t):
		string = input()
		print(optimal_reduction(string))

def optimal_reduction(string):
	chars = Counter(string)
	if len(chars) == 1:
		return len(string)
	elif chars['a'] % 2 == chars['b'] % 2 == chars['c'] % 2:
		return 2
	else:
		return 1
main()


def stringReduction(a):
	starts = [position for position in range(len(a) - 1) if a[position] != a[position + 1]]
	answer = len(a)
	for position in starts:
		answer = min(answer, stringReduction(compress_string(a, position)))
		if answer < 3:
			break
	return answer
translation = {'ab': 'c', 'ba': 'c', 'ac': 'b', 'ca': 'b', 'bc': 'a', 'cb': 'a'}

def compress_string(a, position):
	s = a[position:position + 2]
	return a.replace(s, translation[s])
import sys
f = sys.stdin
t = int(f.readline().strip())
for i in range(0, t):
	a = f.readline().strip()
	print(stringReduction(a))


def stringReduction(a):
	answer = 0
	a_count = 0
	b_count = 0
	c_count = 0
	for c in a:
		if c == 'a':
			a_count += 1
		elif c == 'b':
			b_count += 1
		elif c == 'c':
			c_count += 1
	if a_count % 2 == 0 and b_count % 2 == 0 and (c_count % 2 == 0):
		return 2
	elif a_count % 2 == 1 and b_count % 2 == 1 and (c_count % 2 == 1):
		return 2
	elif a_count > 0 and b_count == c_count == 0:
		return len(a)
	elif b_count > 0 and a_count == c_count == 0:
		return len(a)
	elif c_count > 0 and a_count == b_count == 0:
		return len(a)
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


import collections, sys
char_set = 'abc'
T = int(sys.stdin.readline())
for _ in range(T):
	chars = sys.stdin.readline().lower().strip()
	count = collections.Counter(chars)
	parities = [v % 2 for v in count.values()]
	while len(parities) < len(char_set):
		parities.append(0)
	if len(count.values()) == 1:
		print(len(chars))
	elif len(set(parities)) == 1:
		print(2)
	else:
		print(1)


import collections, sys
char_set = 'abc'
T = int(sys.stdin.readline())
for _ in range(T):
	chars = sys.stdin.readline().lower().strip()
	count = collections.Counter(chars)
	parities = [v % 2 for v in count.values()]
	while len(parities) < len(char_set):
		parities.append(0)
	if len(count.values()) == 1:
		print(len(chars))
	elif len(set(parities)) == 1:
		print(2)
	else:
		print(1)


import collections, sys
char_set = 'abc'
T = int(sys.stdin.readline())
for _ in range(T):
	chars = sys.stdin.readline().lower().strip()
	count = collections.Counter(chars)
	parities = [v % 2 for v in count.values()]
	while len(parities) < len(char_set):
		parities.append(0)
	if len(count.values()) == 1:
		print(len(chars))
	elif len(set(parities)) == 1:
		print(2)
	else:
		print(1)


import collections, sys
char_set = 'abc'
T = int(sys.stdin.readline())
for _ in range(T):
	chars = sys.stdin.readline().lower().strip()
	count = collections.Counter(chars)
	parities = [v % 2 for v in count.values()]
	while len(parities) < len(char_set):
		parities.append(0)
	if len(count.values()) == 1:
		print(len(chars))
	elif len(set(parities)) == 1:
		print(2)
	else:
		print(1)


import collections, sys
char_set = 'abc'
T = int(sys.stdin.readline())
for _ in range(T):
	chars = sys.stdin.readline().lower().strip()
	count = collections.Counter(chars)
	parities = [v % 2 for v in count.values()]
	while len(parities) < len(char_set):
		parities.append(0)
	if len(count.values()) == 1:
		print(len(chars))
	elif len(set(parities)) == 1:
		print(2)
	else:
		print(1)


import collections, sys
char_set = 'abc'
T = int(sys.stdin.readline())
for _ in range(T):
	chars = sys.stdin.readline().lower().strip()
	count = collections.Counter(chars)
	parities = [v % 2 for v in count.values()]
	while len(parities) < len(char_set):
		parities.append(0)
	if len(count.values()) == 1:
		print(len(chars))
	elif len(set(parities)) == 1:
		print(2)
	else:
		print(1)


def count_abc(string):
	a = b = c = 0
	for char in string:
		if char == 'a':
			a += 1
		if char == 'b':
			b += 1
		if char == 'c':
			c += 1
	return (a, b, c)

def is_distinct(string):
	c = string[0]
	for char in string:
		if c != char:
			return False
	return True
for test_cases in range(int(input())):
	string = str(input())
	if is_distinct(string):
		print(len(string))
	else:
		count = count_abc(string)
		if count[0] % 2 == 0 and count[1] % 2 == 0 and (count[2] % 2 == 0) or (count[0] % 2 != 0 and count[1] % 2 != 0 and (count[2] % 2 != 0)):
			print(2)
		else:
			print(1)


def stringReduction(string):
	a = string.count('a')
	b = string.count('b')
	c = string.count('c')
	if [a, b, c].count(0) >= 2:
		return a + b + c
	elif all((v % 2 == 0 for v in [a, b, c])) or all((v % 2 == 1 for v in [a, b, c])):
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def str_len(s):
	if len(set(s)) == 1:
		return len(s)
	else:
		(a, b, c) = (sum((l == 'a' for l in s)), sum((l == 'b' for l in s)), sum((l == 'c' for l in s)))
		if a % 2 == b % 2 and b % 2 == c % 2:
			return 2
		else:
			return 1
for _ in range(int(input())):
	print(str_len(input()))


def stringReduction(s):
	if len(set(s)) == 1:
		return len(s)
	(a, b, c) = (s.count('a'), s.count('b'), s.count('c'))
	is2 = a % 2 == b % 2 == c % 2
	return 2 if is2 else 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	x = y = z = 0
	l = len(a)
	if l == 1:
		return l
	for i in range(0, l):
		if a[i] == 'a':
			x += 1
		if a[i] == 'b':
			y += 1
		if a[i] == 'c':
			z += 1
	if x == 0:
		return r(y, z, l)
	if y == 0:
		return r(x, z, l)
	if z == 0:
		return r(x, y, l)
	if x % 2 == y % 2 == z % 2:
		return 2
	else:
		return 1

def r(x, y, l):
	if x == 0 or y == 0:
		return l
	if x % 2 == y % 2 == 0:
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(A):
	if len(set(A)) == 1:
		return len(A)
	L = [A.count(i) for i in 'abc']
	S = sum((l % 2 for l in L))
	if S == 0 or S == 3:
		return 2
	return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	if len(set(a)) == 1:
		return len(a)
	counts = {'a': a.count('a'), 'b': a.count('b'), 'c': a.count('c')}
	evens = counts['a'] % 2 == 0
	evens += counts['b'] % 2 == 0
	evens += counts['c'] % 2 == 0
	answer = 0
	if evens == 3 or evens == 0:
		answer = 2
	else:
		answer = 1
	return answer
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


t = int(input())

def stringReduction(s):
	(a, b, c) = [0] * 3
	for e in s:
		if e == 'a':
			a += 1
		elif e == 'b':
			b += 1
		else:
			c += 1
	if [a, b, c].count(0) > 1:
		return len(s)
	else:
		l = list(map(lambda x: x % 2, [a, b, c]))
		if l.count(0) == 3 or l.count(1) == 3:
			return 2
		else:
			return 1
	print(a, b, c)
for _ in range(t):
	text = input()
	print(stringReduction(text))


def stringReduction(string):
	a = string.count('a')
	b = string.count('b')
	c = string.count('c')
	if [a, b, c].count(0) >= 2:
		return a + b + c
	elif all((v % 2 == 0 for v in [a, b, c])) or all((v % 2 == 1 for v in [a, b, c])):
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	answer = 0
	numA = list(a).count('a')
	numB = list(a).count('b')
	numC = list(a).count('c')
	if numA == len(a) or numB == len(a) or numC == len(a):
		answer = len(a)
	elif numA % 2 == 0 and numB % 2 == 0 and (numC % 2 == 0) or (numA % 2 == 1 and numB % 2 == 1 and (numC % 2 == 1)):
		answer = 2
	else:
		answer = 1
	return answer
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(arr):
	answer = 0
	a = 0
	b = 0
	c = 0
	for each in arr:
		if each == 'a':
			a += 1
		elif each == 'b':
			b += 1
		else:
			c += 1
	if a == 0 and b == 0 or (b == 0 and c == 0) or (a == 0 and c == 0):
		return a + b + c
	elif a % 2 == 0 and b % 2 == 0 and (c % 2 == 0) or (a % 2 == 1 and b % 2 == 1 and (c % 2 == 1)):
		return 2
	else:
		return 1
	return answer
t = int(input())
for i in range(0, t):
	a = list(input())
	print(stringReduction(a))


T = int(input())
for _ in range(T):
	chars = input()
	counts = [0, 0, 0]
	for char in chars:
		if char == 'a':
			counts[0] += 1
		elif char == 'b':
			counts[1] += 1
		else:
			counts[2] += 1
	for count in counts:
		if count == len(chars):
			print(len(chars))
			break
	else:
		odds = 0
		evens = 0
		for count in counts:
			if count % 2 == 0:
				evens += 1
			else:
				odds += 1
		if evens == 3 or odds == 3:
			print(2)
		else:
			print(1)


t = int(input())
for _ in range(t):
	st = input()
	n = len(st)
	a = 0
	b = 0
	c = 0
	for i in range(len(st)):
		if st[i] == 'a':
			a += 1
		if st[i] == 'b':
			b += 1
		if st[i] == 'c':
			c += 1
	if a == n or b == n or c == n:
		print(n)
	elif a % 2 == 0 and b % 2 == 0 and (c % 2 == 0) or (a % 2 and b % 2 and c % 2):
		print(2)
	else:
		print(1)


def cnt(x):
	m = {}
	m['a'] = 0
	m['b'] = 0
	m['c'] = 0
	for c in x:
		if c not in m:
			m[c] = 1
		else:
			m[c] += 1
	return m

def red(x):
	xm = cnt(x)
	if xm['a'] == 0 and xm['b'] == 0 or (xm['a'] == 0 and xm['c'] == 0) or (xm['a'] == 0 and xm['c'] == 0):
		return len(x)
	if xm['a'] % 2 == 0 and xm['b'] % 2 == 0 and (xm['c'] % 2 == 0) or (xm['a'] % 2 == 1 and xm['b'] % 2 == 1 and (xm['c'] % 2 == 1)):
		return 2
	return 1
for i in range(0, int(input())):
	x = input()
	print(red(x))


def occur(a):
	(ca, cb, cc) = (0, 0, 0)
	for i in a:
		if i == 'a':
			ca += 1
		elif i == 'b':
			cb += 1
		else:
			cc += 1
	return [ca, cb, cc]
for i in range(int(input())):
	a = input()
	s = occur(a)
	if s[0] + s[1] == 0 or s[1] + s[2] == 0 or s[2] + s[0] == 0:
		print(len(a))
	elif s[0] % 2 == 0 and s[1] % 2 == 0 and (s[2] % 2 == 0):
		print(2)
	elif s[0] % 2 != 0 and s[1] % 2 != 0 and (s[2] % 2 != 0):
		print(2)
	else:
		print(1)


import collections, sys
char_set = 'abc'
T = int(sys.stdin.readline())
for _ in range(T):
	chars = sys.stdin.readline().lower().strip()
	count = collections.Counter(chars)
	parities = [v % 2 for v in count.values()]
	while len(parities) < len(char_set):
		parities.append(0)
	if len(count.values()) == 1:
		print(len(chars))
	elif len(set(parities)) == 1:
		print(2)
	else:
		print(1)


z = []
for i in range(int(input())):
	z.append(input())
for i in z:
	a = i.count('a')
	b = i.count('b')
	c = i.count('c')
	if a == len(i) or b == len(i) or c == len(i):
		print(len(i))
	elif a % 2 == 0 and b % 2 == 0 and (c % 2 == 0) or (a % 2 != 0 and b % 2 != 0 and (c % 2 != 0)):
		print(2)
	else:
		print(1)


def stringReduction(a):
	a_count = a.count('a')
	b_count = a.count('b')
	c_count = a.count('c')
	if len(a) in (a_count, b_count, c_count):
		answer = len(a)
	elif a_count % 2 == b_count % 2 == c_count % 2:
		answer = 2
	else:
		answer = 1
	return answer
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	answer = 0
	count_a = a.count('a')
	count_b = a.count('b')
	count_c = a.count('c')
	string_length = len(a)
	if count_a == string_length or count_b == string_length or count_c == string_length:
		answer = string_length
	elif count_a % 2 == 1 and count_b % 2 == 1 and (count_c % 2 == 1) or (count_a % 2 == 0 and count_b % 2 == 0 and (count_c % 2 == 0)):
		answer = 2
	else:
		answer = 1
	return answer
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


n = int(input().strip())
arr = []
for i in range(n):
	arr.append(input().strip())

def count_abc(x):
	vector = [0, 0, 0]
	for i in x:
		if i == 'a':
			vector[0] += 1
		elif i == 'b':
			vector[1] += 1
		else:
			vector[2] += 1
	return vector

def check_parity(vector):
	return 1 + ((vector[0] + vector[1]) % 2 == 0 and (vector[0] + vector[2]) % 2 == 0)

def check_repunit(my_string):
	repunit = my_string[0] * len(my_string)
	return (my_string == repunit) * len(my_string)
for my_string in arr:
	k = check_repunit(my_string)
	if k:
		print(k)
	else:
		print(check_parity(count_abc(my_string)))


from collections import Counter
for _ in range(int(input())):
	k = input()
	r = Counter(k)
	if len(r) == 1:
		print(len(k))
	elif r['a'] % 2 == r['b'] % 2 == r['c'] % 2:
		print(2)
	else:
		print(1)


def stringReduction(text):
	numl = [0] * 3
	for l in text:
		if l == 'a':
			numl[0] += 1
		elif l == 'b':
			numl[1] += 1
		else:
			numl[2] += 1
	numl.sort()
	if numl[1] == 0:
		return len(text)
	summod = sum([n % 2 for n in numl])
	if summod in [0, 3]:
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	counts = {x: a.count(x) for x in set(a)}
	zeros = [1 for x in counts if counts[x] == 0]
	odds = [x for x in counts if counts[x] % 2 == 1]
	if len(counts) == 1:
		return len(a)
	elif len(odds) == 1 or len(odds) == 2:
		return 1
	else:
		return 2
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	if all((l == 'a' for l in a)) or all((l == 'b' for l in a)) or all((l == 'c' for l in a)):
		return len(a)
	if all((a.count(l) % 2 for l in 'abc')) or not any((a.count(l) % 2 for l in 'abc')):
		return 2
	return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


from collections import Counter

def stringReduction(a):
	count = Counter(a)
	if len(count) == 1:
		return len(a)
	elif count['a'] % 2 == 0 and count['b'] % 2 == 0 and (count['c'] % 2 == 0):
		return 2
	elif count['a'] % 2 != 0 and count['b'] % 2 != 0 and (count['c'] % 2 != 0):
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


n = int(input())
for i in range(n):
	s = input()
	g = 0
	d = 0
	f = 0
	for j in range(len(s)):
		if s[j] == 'a':
			g += 1
		elif s[j] == 'b':
			d += 1
		else:
			f += 1
	if g == len(s) or f == len(s) or d == len(s):
		print(len(s))
	elif g % 2 == 0 and d % 2 == 0 and (f % 2 == 0) or (g % 2 != 0 and d % 2 != 0 and (f % 2 != 0)):
		print(2)
	else:
		print(1)


def stringReduction(s):
	num_a = num_b = num_c = 0
	for char in s:
		if char == 'a':
			num_a += 1
		elif char == 'b':
			num_b += 1
		else:
			num_c += 1
	if len(s) == num_a or len(s) == num_b or len(s) == num_c:
		answer = len(s)
	elif num_a % 2 == 0 and num_b % 2 == 0 and (num_c % 2 == 0):
		answer = 2
	elif num_a % 2 == 1 and num_b % 2 == 1 and (num_c % 2 == 1):
		answer = 2
	else:
		answer = 1
	return answer
t = int(input())
for i in range(t):
	s = input()
	print(stringReduction(s))


def stringReduction(a):
	answer = len(a)
	a_s = a.count('a')
	b_s = a.count('b')
	c_s = a.count('c')
	if a_s + b_s == 0 or a_s + c_s == 0 or b_s + c_s == 0:
		return len(a)
	if a_s % 2 == 0 and b_s % 2 == 0 and (c_s % 2 == 0):
		return 2
	if a_s % 2 == 1 and b_s % 2 == 1 and (c_s % 2 == 1):
		return 2
	return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	answer = 0
	a = list(a)
	d = dict()
	flag = 1
	d['a'] = 0
	d['b'] = 0
	d['c'] = 0
	for x in a:
		if x in d:
			d[x] += 1
		else:
			d[x] = 1
	if d['a'] == len(a) or d['b'] == len(a) or d['c'] == len(a):
		return len(a)
	if d['a'] % 2 == 0 and d['b'] % 2 == 0 and (d['c'] % 2 == 0) or (d['a'] % 2 != 0 and d['b'] % 2 != 0 and (d['c'] % 2 != 0)):
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	answer = 0
	num_a = a.count('a')
	num_b = a.count('b')
	num_c = a.count('c')
	parity_a = num_a % 2 == 0
	parity_b = num_b % 2 == 0
	parity_c = num_c % 2 == 0
	if len(set(a)) == 1:
		answer = len(a)
	else:
		answer = 2 if parity_a == parity_b == parity_c else 1
	return answer
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	acount = a.count('a')
	bcount = a.count('b')
	ccount = a.count('c')
	if [acount, bcount, ccount].count(0) >= 2:
		return acount + bcount + ccount
	elif all((v % 2 == 0 for v in [acount, bcount, ccount])) or all((v % 2 == 1 for v in [acount, bcount, ccount])):
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


import collections, sys
char_set = 'abc'
T = int(sys.stdin.readline())
for _ in range(T):
	chars = sys.stdin.readline().lower().strip()
	count = collections.Counter(chars)
	parities = [v % 2 for v in count.values()]
	while len(parities) < len(char_set):
		parities.append(0)
	if len(count.values()) == 1:
		print(len(chars))
	elif len(set(parities)) == 1:
		print(2)
	else:
		print(1)


import itertools

def collapse(string):
	letters = {'a': 0, 'b': 0, 'c': 0}
	for letter in string:
		letters[letter] += 1
	return letters

def simplify(letters):
	lrg = max(letters.items(), key=lambda x: x[1])[0]
	sml = min(letters.items(), key=lambda x: x[1])[0]
	if sml == lrg:
		return 2
	for k in letters.keys():
		if k not in [lrg, sml]:
			mid = k
			break
	if not letters[mid]:
		return letters[lrg]
	letters[lrg] -= 1
	letters[mid] -= 1
	letters[sml] += 1
	return None

def string_reduction(string):
	letters = collapse(string)
	value = None
	while value is None:
		value = simplify(letters)
	return value
for _ in range(int(input())):
	string = input().strip()
	print(string_reduction(string))


from collections import Counter
answers = []
for _ in range(int(input())):
	c = Counter(input().strip())
	l = len(c)
	vals = list(c.values())
	equal_diss = True
	if l == 1:
		answers.append(str(vals[0]))
	elif l == 2:
		for e in vals:
			if e % 2 != 0:
				equal_diss = False
				break
		answers.append('2' if equal_diss else '1')
	else:
		diss = vals[0] % 2
		for e in vals[1:]:
			if e % 2 != diss:
				equal_diss = False
				break
		answers.append('2' if equal_diss else '1')
print('\n'.join(answers))


def nc(a, b):
	if a == 'a':
		if b == 'b':
			return 'c'
		else:
			return 'b'
	elif a == 'b':
		if b == 'a':
			return 'c'
		else:
			return 'a'
	elif b == 'a':
		return 'b'
	else:
		return 'a'

def possibilities(a):
	ns = []
	for i in range(len(a) - 1):
		if a[i] != a[i + 1]:
			ns.append(a[:i] + nc(a[i], a[i + 1]) + a[i + 2:])
	return set(ns)
C = {}

def stringReduction(a):
	if a in C:
		return C[a]
	answer = None
	ps = possibilities(a)
	if len(ps) == 0:
		return len(a)
	for a1 in ps:
		na = stringReduction(a1)
		if na == 1:
			answer = na
			break
		elif answer is None or answer > na:
			answer = na
	C[a] = answer
	return answer

def stringReduction(s):
	a = len([_ for _ in s if _ == 'a'])
	b = len([_ for _ in s if _ == 'b'])
	c = len([_ for _ in s if _ == 'c'])
	return arrReduction([a, b, c])

def arrReduction(a):
	nonuls = [_ for _ in a if _ != 0]
	if len(nonuls) == 0:
		return 0
	elif len(nonuls) == 1:
		return nonuls[0]
	maxV = max(a)
	minV = min(a)
	if maxV == minV:
		maxVi = 0
		minVi = 1
		othVi = 2
	else:
		maxVi = a.index(maxV)
		minVi = a.index(minV)
		othVi = list(set([0, 1, 2]).difference(set([maxVi, minVi])))[0]
	na = a[:]
	na[maxVi] -= 1
	na[othVi] -= 1
	na[minVi] += 1
	return arrReduction(na)
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


from functools import reduce

def stringReduction(count):
	count.sort(reverse=True)
	return stringReduction([count[0] - 1, count[1] - 1, count[2] + 1]) if count[1] != 0 else sum(count)
t = int(input())
for i in range(0, t):
	a = input()
	count = [a.count('a'), a.count('b'), a.count('c')]
	print(stringReduction(count))


def stringReduction(a):
	counts = [a.count('a'), a.count('b'), a.count('c')]
	if counts.count(0) >= 2:
		return sum(counts)
	evenness = sum([count % 2 for count in counts])
	if evenness == 0 or evenness == 3:
		return 2
	return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(foo):
	a = foo.count('a')
	b = foo.count('b')
	c = foo.count('c')
	if max(a, b, c) == a + b + c:
		return len(foo)
	if a % 2 == b % 2 and c % 2 == b % 2:
		return 2
	return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(s):
	(a, b, c) = (s.count('a'), s.count('b'), s.count('c'))
	letters = [l for l in [a, b, c]]
	if a == len(s) or b == len(s) or c == len(s):
		answer = len(s)
	elif all(map(lambda x: x % 2 == 0, letters)) or all(map(lambda x: x % 2 != 0, letters)):
		answer = 2
	else:
		answer = 1
	return answer
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	answer = 0
	count1 = a.count('a')
	count2 = a.count('b')
	count3 = a.count('c')
	if count1 == len(a) or count2 == len(a) or count3 == len(a):
		return len(a)
	if count1 % 2 == 0 and count2 % 2 == 0 and (count3 % 2 == 0) or (count1 % 2 == 1 and count2 % 2 == 1 and (count3 % 2 == 1)):
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	countA = a.count('a')
	countB = a.count('b')
	countC = a.count('c')
	if countA == len(a) or countB == len(a) or countC == len(a):
		return len(a)
	if countA % 2 == 0 and countB % 2 == 0 and (countC % 2 == 0):
		return 2
	if countA % 2 == 1 and countB % 2 == 1 and (countC % 2 == 1):
		return 2
	return 1
t = int(input())
for i in range(0, t):
	a = input()
	a = a.strip()
	print(stringReduction(a))


from collections import defaultdict

def getLengthOfStringReduction(s):
	d = defaultdict(int)
	for c in s:
		d[c] += 1
	if d['a'] == len(s) or d['b'] == len(s) or d['c'] == len(s):
		return len(s)
	elif d['a'] % 2 == 0 and d['b'] % 2 == 0 and (d['c'] % 2 == 0) or (d['a'] % 2 != 0 and d['b'] % 2 != 0 and (d['c'] % 2 != 0)):
		return 2
	else:
		return 1
t = int(input().strip())
assert 1 <= t <= 100, 'too many test cases'
for i in range(t):
	s = input().strip()
	assert len(s) <= 100, 'string too long'
	print(getLengthOfStringReduction(s))


def stringReduction(a):
	answer = 0
	flag = False
	for i in range(1, len(a)):
		if a[i] != a[i - 1]:
			flag = True
			break
	if not flag:
		answer = len(a)
	else:
		c_a = 0
		c_b = 0
		c_c = 0
		for x in a:
			if x == 'a':
				c_a += 1
			elif x == 'b':
				c_b += 1
			else:
				c_c += 1
		if c_a % 2 == 0 and c_b % 2 == 0 and (c_c % 2 == 0) or (c_a % 2 == 1 and c_b % 2 == 1 and (c_c % 2 == 1)):
			answer = 2
		else:
			answer = 1
	return answer
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(strData):
	allsame = False
	strLen = len(strData)
	if strData.count('a') == strLen or strData.count('b') == strLen or strData.count('c') == strLen:
		return len(strData)
	else:
		countArr = []
		for s in ['a', 'b', 'c']:
			countArr.append(strData.count(s))
		allodd = True
		alleven = True
		for count in countArr:
			if count % 2 == 0:
				allodd = False
			elif count % 2 != 0:
				alleven = False
		if alleven or allodd:
			return 2
		else:
			return 1
t = int(input())
if t >= 1 and t <= 100:
	for i in range(t):
		a = input()
		if len(a) <= 100:
			print(stringReduction(a))


import itertools
bestPartDict = dict()
bestPartDict['a'] = 'a'
bestPartDict['b'] = 'b'
bestPartDict['c'] = 'c'
bestPartDict['aa'] = 'aa'
bestPartDict['bb'] = 'bb'
bestPartDict['cc'] = 'cc'
bestPartDict['ab'] = 'c'
bestPartDict['ba'] = 'c'
bestPartDict['bc'] = 'a'
bestPartDict['cb'] = 'a'
bestPartDict['ac'] = 'b'
bestPartDict['ca'] = 'b'

def stringReduction(a):
	abc = [0, 0, 0]
	n = len(a)
	for i in a:
		if i == 'a':
			abc[0] += 1
		elif i == 'b':
			abc[1] += 1
		else:
			abc[2] += 1
	if abc[0] == n or abc[1] == n or abc[2] == n:
		return n
	if abc[0] % 2 == 0 and abc[1] % 2 == 0 and (abc[2] % 2 == 0) or (abc[0] % 2 == 1 and abc[1] % 2 == 1 and (abc[2] % 2 == 1)):
		return 2
	return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


for a0 in range(int(input())):
	A = input()
	counts = [A.count('a'), A.count('b'), A.count('c')]
	if counts.count(0) == 2:
		print(len(A))
	elif counts[0] % 2 == counts[1] % 2 == counts[2] % 2:
		print(2)
	else:
		print(1)


from collections import Counter
t = int(input())

def strreduce(a):
	c = Counter(a)
	if len(c) == 1:
		return len(a)
	if c['a'] % 2 == c['b'] % 2 == c['c'] % 2:
		return 2
	else:
		return 1
for _ in range(t):
	a = input()
	answer = strreduce(a)
	print(answer)


def stringReduction(a):
	(x, y, z) = (0, 0, 0)
	for i in a:
		if i == 'a':
			x += 1
		elif i == 'b':
			y += 1
		else:
			z += 1
	if x == len(a) or y == len(a) or z == len(a):
		return len(a)
	if x % 2 == y % 2 and y % 2 == z % 2:
		return 2
	return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	nA = a.count('a')
	nB = a.count('b')
	nC = a.count('c')
	if nA == 0 and nB == 0 or (nB == 0 and nC == 0) or (nC == 0 and nA == 0):
		return len(a)
	elif nA % 2 == 0 and nB % 2 == 0 and (nC % 2 == 0):
		return 2
	elif nA % 2 == 1 and nB % 2 == 1 and (nC % 2 == 1):
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	if sorted(a) == sorted(a, reverse=True):
		return len(a)
	if a.count('a') % 2 == a.count('b') % 2 == a.count('c') % 2:
		return 2
	return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


import collections as collect

def len1(n):
	if n['a'] + n['b'] == 0 or n['a'] + n['c'] == 0 or n['b'] + n['c'] == 0:
		return n['a'] + n['b'] + n['c']
	temp = min(n['a'], n['b'], n['c'])
	if n['a'] == temp:
		n['a'] = n['a'] + 1
		n['b'] = n['b'] - 1
		n['c'] = n['c'] - 1
		return len1(n)
	if n['b'] == temp:
		n['a'] = n['a'] - 1
		n['b'] = n['b'] + 1
		n['c'] = n['c'] - 1
		return len1(n)
	if n['c'] == temp:
		n['a'] = n['a'] - 1
		n['b'] = n['b'] - 1
		n['c'] = n['c'] + 1
		return len1(n)
t = int(input())
for i in range(0, t):
	a = input()
	print(len1(collect.Counter(a)))


def stringReduction(word):
	a = 0
	b = 0
	c = 0
	for letter in word:
		if letter == 'a':
			a += 1
		elif letter == 'b':
			b += 1
		else:
			c += 1
	if a == 0 and b == 0 or (a == 0 and c == 0) or (b == 0 and c == 0):
		return len(word)
	elif a % 2 == 0 and b % 2 == 0 and (c % 2 == 0):
		return 2
	elif a % 2 == 1 and b % 2 == 1 and (c % 2 == 1):
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


import collections, sys
char_set = 'abc'
T = int(sys.stdin.readline())
for _ in range(T):
	chars = sys.stdin.readline().lower().strip()
	count = collections.Counter(chars)
	parities = [v % 2 for v in count.values()]
	while len(parities) < len(char_set):
		parities.append(0)
	if len(count.values()) == 1:
		print(len(chars))
	elif len(set(parities)) == 1:
		print(2)
	else:
		print(1)


from collections import defaultdict

def stringReduction(a):
	N = len(a)
	scount = defaultdict(int)
	for i in a:
		scount[i] += 1
	ch = 3
	while ch > 1:
		ch = sum(map(lambda x: 1 if x > 0 else 0, scount.values()))
		if scount['a'] >= scount['b'] and scount['b'] >= scount['c']:
			scount['a'] -= 1
			scount['b'] -= 1
			scount['c'] += 1
		elif scount['a'] >= scount['c'] and scount['c'] >= scount['b']:
			scount['a'] -= 1
			scount['c'] -= 1
			scount['b'] += 1
		elif scount['b'] >= scount['a'] and scount['a'] >= scount['c']:
			scount['a'] -= 1
			scount['b'] -= 1
			scount['c'] += 1
		elif scount['b'] >= scount['c'] and scount['c'] >= scount['a']:
			scount['c'] -= 1
			scount['b'] -= 1
			scount['a'] += 1
		elif scount['c'] >= scount['a'] and scount['a'] >= scount['b']:
			scount['c'] -= 1
			scount['a'] -= 1
			scount['b'] += 1
		elif scount['c'] >= scount['b'] and scount['b'] >= scount['a']:
			scount['c'] -= 1
			scount['b'] -= 1
			scount['a'] += 1
	return sum(scount.values()) + 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	aa = a.count('a')
	bb = a.count('b')
	cc = a.count('c')
	if aa == bb == 0 or aa == cc == 0 or bb == cc == 0:
		answer = len(a)
	elif aa % 2 == bb % 2 == cc % 2:
		answer = 2
	else:
		answer = 1
	return answer
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(a):
	s = list(a.strip())
	numa = 0
	numb = 0
	numc = 0
	for i in range(0, len(s)):
		if s[i] == 'a':
			numa += 1
		elif s[i] == 'b':
			numb += 1
		else:
			numc += 1
	if numa == len(s) or numb == len(s) or numc == len(s):
		return len(s)
	elif numa % 2 == 0 and numb % 2 == 0 and (numc % 2 == 0) or (numa % 2 == 1 and numb % 2 == 1 and (numc % 2 == 1)):
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


t = int(input())
for i in range(t):
	count = [0] * 3
	string = input()
	for j in range(len(string)):
		if string[j] == 'a':
			count[0] += 1
		elif string[j] == 'b':
			count[1] += 1
		elif string[j] == 'c':
			count[2] += 1
	while sum(count) != count[0] and sum(count) != count[1] and (sum(count) != count[2]):
		smallest = count.index(min(count))
		count[smallest] += 1
		for x in range(3):
			if x != smallest:
				count[x] -= 1
	print(sum(count))


def stringReduction(a):
	ac = 0
	bc = 0
	cc = 0
	for s in a:
		if s == 'a':
			ac += 1
		elif s == 'b':
			bc += 1
		else:
			cc += 1
	if ac == 0 and bc == 0:
		return cc
	if bc == 0 and cc == 0:
		return ac
	if cc == 0 and ac == 0:
		return bc
	ae = ac % 2 == 0
	be = bc % 2 == 0
	ce = cc % 2 == 0
	if ae == be and be == ce:
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))


def stringReduction(stringa):
	a = stringa.count('a')
	b = stringa.count('b')
	c = stringa.count('c')
	if a == len(stringa):
		return a
	if b == len(stringa):
		return b
	if c == len(stringa):
		return c
	if a % 2 == 0 and b % 2 == 0 and (c % 2 == 0):
		answer = 2
	elif a % 2 == 1 and b % 2 == 1 and (c % 2 == 1):
		answer = 2
	else:
		answer = 1
	return answer
t = int(input())
for i in range(0, t):
	stringa = input()
	print(stringReduction(stringa))


def stringReduction(s):
	occ = [s.count('a'), s.count('b'), s.count('c')]
	if occ.count(0) == 2:
		return len(s)
	elif occ[0] % 2 == occ[1] % 2 == occ[2] % 2:
		return 2
	else:
		return 1
t = int(input())
for i in range(0, t):
	a = input()
	print(stringReduction(a))