The title is a reference to the very first Educational Round from our writers team, Educational Round 18.

There is a bag, containing colored balls. There are $n$ different colors of balls, numbered from $1$ to $n$. There are $\mathit{cnt}_i$ balls of color $i$ in the bag. The total amount of balls in the bag is odd (e. g. $\mathit{cnt}_1 + \mathit{cnt}_2 + \dots + \mathit{cnt}_n$ is odd).

In one move, you can choose two balls with different colors and take them out of the bag.

At some point, all the remaining balls in the bag will have the same color. That's when you can't make moves anymore.

Find any possible color of the remaining balls.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 20$) — the number of colors.

The second line contains $n$ integers $\mathit{cnt}_1, \mathit{cnt}_2, \dots, \mathit{cnt}_n$ ($1 \le \mathit{cnt}_i \le 100$) — the amount of balls of each color in the bag.

The total amount of balls in the bag is odd (e. g. $\mathit{cnt}_1 + \mathit{cnt}_2 + \dots + \mathit{cnt}_n$ is odd).


-----Output-----

For each testcase, print a single integer — any possible color of the remaining balls, after you made some moves and can't make moves anymore.


-----Examples-----

Input
3
3
1 1 1
1
9
2
4 7
Output
3
1
2


-----Note-----

In the first testcase, your first and only move can be one of the following:

take balls with colors $1$ and $2$;

take balls with colors $1$ and $3$;

take balls with colors $2$ and $3$.

After the move, exactly one ball will remain. Its color can be $3, 2$ or $1$ depending on the move.

In the second testcase, you can't make moves at all — there is only color of balls already. This color is $1$.

In the third testcase, you can keep removing one ball of color $1$ and one ball of color $2$ until there are no more balls of color $1$. At the end, three balls of color $2$ remain.

Difficulty: EASY
Tags: Complete search

Sorting

Implementation

Greedy algorithms
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	ma = max(l)
	print(l.index(ma) + 1)


import sys
input = sys.stdin.readline
tests = int(input())
for test in range(tests):
	n = int(input())
	a = list(map(int, input().split()))
	print(1 + a.index(max(a)))


output = ''
for caseno in range(int(input())):
	n = int(input())
	l = map(int, input().split())
	cur_max = 0
	answer = -1
	for (ind, val) in enumerate(l):
		if val > cur_max:
			cur_max = val
			answer = ind + 1
	output += str(answer) + '\n'
print(output)


t = int(input())
for i in range(t):
	n = int(input())
	s = input().split(' ')
	cnt = list(map(int, s))
	print(cnt.index(max(cnt)) + 1)


def solve():
	n = int(input())
	arr = [int(x) for x in input().split()]
	max_idx = 0
	max_num = arr[0]
	for i in range(1, n):
		if arr[i] > max_num:
			max_num = arr[i]
			max_idx = i
	print(max_idx + 1)
t = int(input())
for _ in range(t):
	solve()


n = int(input())
for i in range(n):
	m = int(input())
	v = list(map(int, input().split()))
	p = 0
	for j in range(m):
		if v[j] > p:
			p = v[j]
			q = j
	print(q + 1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(a.index(max(a)) + 1)


t = int(input())
for testcase in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(arr.index(max(arr)) + 1)


no_of_cases = int(input())
a = no_of_cases
cases = []
fullcase = []
while a > 0:
	cases.append(int(input()))
	b = input().split()
	c = []
	for i in b:
		c.append(int(i))
	fullcase.append(c)
	a = a - 1
for i in fullcase:
	max = 0
	index = 0
	for j in i:
		index = index + 1
		if j > max:
			max = j
			maxindex = index
	print(maxindex)


k = int(input())
for j in range(k):
	s = int(input())
	t = list(map(int, input().split()))
	r = max(t)
	print(t.index(r) + 1)


a = int(input())
for i in range(a):
	_ = input()
	arr = [int(x) for x in input().split()]
	print(arr.index(max(arr)) + 1)


t = int(input())
for i in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	max = 0
	for j in x:
		if max < j:
			max = j
	j = 0
	while j < n:
		if max == x[j]:
			print(j + 1)
			break
		j = j + 1


import sys
input = sys.stdin.readline
N = int(input())
for _ in range(N):
	_ = int(input())
	C = list(map(int, input().split()))
	maxv = max(C)
	print(C.index(maxv) + 1)


n = int(input())
p = []
for j in range(n):
	m = int(input())
	A = list(map(int, input().split()))
	h = max(A)
	t = A.index(h)
	p.append(t)
for y in p:
	print(y + 1)


def sol(l):
	if len(l) == 1:
		return 1
	else:
		return l.index(max(l)) + 1
t = int(input())
for _ in range(t):
	n = input()
	l = [int(i) for i in input().split()]
	print(sol(l))


for s in [*open(0)][2::2]:
	a = s.split()
	print(a.index(max(a, key=int)) + 1)


for S in [*open(0)][2::2]:
	x = S.split()
	print(x.index(max(x, key=int)) + 1)


t = int(input())
for i in range(t):
	n = int(input())
	cnt = list(map(int, input().split()))
	index = 1
	a = cnt[0]
	for i in range(n):
		if cnt[i] > a:
			a = cnt[i]
			index = i + 1
	print(index)


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = int(input())
	s = input()
	a = [int(i) for i in s.split(' ')]
	ans = max(range(len(a)), key=a.__getitem__)
	print(ans + 1)
	t -= 1


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(a.index(max(a)) + 1)


def num():
	c = int(input())
	return c

def stri():
	c = str(input())
	return c

def vector():
	c = list(map(int, input().split()))
	return c

def strvector():
	c = list(map(str, input().split()))
	return c
import math
from collections import defaultdict

def isprime(num):
	a = 2
	while a <= math.sqrt(num):
		if num % a < 1:
			return False
		a = a + 1
	return num > 1
t = num()
while t > 0:
	t -= 1
	n = num()
	arr = vector()
	c = max(arr)
	x = arr.index(c)
	print(x + 1)


import sys, math
input = sys.stdin.readline
INF = int(1000000000.0) + 7
MOD = 998244353

def solve():
	n = int(input())
	data = list(map(int, input().split()))
	mx = max(data)
	for i in range(n):
		if data[i] == mx:
			print(i + 1)
			return
t = 1
t = int(input())
for i in range(1, t + 1):
	solve()


for _ in range(int(input())):
	n = int(input())
	nums = [int(i) for i in input().split()]
	print(nums.index(max(nums)) + 1)


for _ in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	a = 0
	b = 0
	for i in range(x):
		if y[i] > a:
			a = y[i]
			b = i + 1
	print(b)


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)

def Solve():
	for t in range(int(input())):
		n = int(input())
		cnt = list(map(int, input().split()))
		print(cnt.index(max(cnt)) + 1)
Solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(a.index(max(a)) + 1)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	maxInd = -1
	maxx = -100
	for i in range(n):
		if maxx < a[i]:
			maxx = a[i]
			maxInd = i
	print(maxInd + 1)


for t in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	summ = sum(s)
	m = max(s)
	if m * 2 > summ:
		print(s.index(m) + 1)
	else:
		print(1)


a = int(input())
for i in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	print(c.index(max(c)) + 1)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

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

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for _ in range(t):
	n = inp()
	l = li()
	m = 0
	for i in range(n):
		if l[i] > m:
			k = i
			m = l[i]
	print(k + 1)


n = int(input())
for _ in range(n):
	a = int(input())
	b = list(map(int, input().strip().split()))
	c = max(b)
	print(b.index(c) + 1)


for t in range(0, int(input())):
	n = int(input())
	my_list = list(map(int, input().split()))
	max_ = max(my_list)
	print(my_list.index(max_) + 1)


t = int(input())
for r in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(l.index(max(l)) + 1)


n = int(input())
for p in range(0, n):
	m = int(input())
	a = list(map(int, input().split()))
	l = max(a)
	c = a.index(l)
	print(c + 1)


n = int(input())
for _ in range(n):
	k = int(input())
	p = list(map(int, input().split()))
	print(p.index(max(p)) + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	print(l.index(m) + 1)


ad = int(input())
for i in range(ad):
	n = int(input())
	a = list(map(int, input().split()))
	ma = 0
	mai = 1
	r = a.index(max(a))
	print(r + 1)


def solution(x):
	mx = 0
	idx = 0
	for i in range(len(x)):
		if x[i] > mx:
			mx = x[i]
			idx = i
	return idx
T = int(input().strip())
while T > 0:
	T -= 1
	n = int(input().strip())
	x = list(map(int, input().strip().split()))
	print(solution(x) + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = [int(x) for x in input().split()]
	print(s.index(max(s)) + 1)


def maximum(a):
	i = 0
	temp = 0
	maximum = a[0]
	for i in range(1, len(a)):
		if a[i] > maximum:
			maximum = a[i]
			temp = i
	return temp + 1
t = int(input())
arr1 = []
for i in range(t):
	arr = []
	n = int(input())
	arr = list(map(int, input().split(sep=' ')))
	arr1.append(maximum(arr))
for i in range(t):
	print(arr1[i])


a = int(input())
for i in range(a):
	col = int(input())
	if col == 1:
		b = int(input())
		print(1)
	else:
		P = list(map(int, input().split()))
		print(P.index(max(P)) + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	ma = max(x)
	print(x.index(ma) + 1)


res = []
t = int(input())
for i in range(t):
	n = int(input())
	balls = [int(x) for x in input().split()]
	res.append(balls.index(max(balls)) + 1)
print(*res, sep='\n')


answer = []
for i in range(int(input())):
	kc = int(input())
	ksh = list(map(int, input().split()[:kc]))
	answer.append(ksh.index(max(ksh)) + 1)
print(*answer, sep='\n')


from operator import indexOf
results = []
naborov = int(input())
for i in range(0, naborov):
	k = int(input())
	mas = list(map(int, input().split()))
	results.append(mas.index(max(mas)) + 1)
for res in results:
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	i = arr.index(max(arr))
	print(i + 1)


for _ in ' ' * int(input()):
	_ = input()
	x = list(map(int, input().split()))
	print(x.index(max(x)) + 1)


n = int(input())
l = []
for i in range(n):
	l = []
	nc = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	print(l.index(m) + 1)


testcases = int(input())
for eachcase in range(testcases):
	length = int(input())
	array = list(map(int, input().split()))
	maxcolor = 1
	index = 1
	for color in range(length):
		if maxcolor < array[color]:
			maxcolor = array[color]
			index = color + 1
	print(index)


from sys import stdin, stdout

def solve():
	n = int(stdin.readline())
	cnt = list(map(int, stdin.readline().split()))
	(m, index) = (0, 0)
	for i in range(n):
		if cnt[i] > m:
			m = cnt[i]
			index = i + 1
	print(index)

def main():
	t = stdin.readline()
	for i in range(int(t)):
		solve()
main()


import sys
arr = []
for line in sys.stdin:
	nums = [int(x) for x in line.strip().split()]
	for j in nums:
		arr.append(j)
test_cases = arr[0]
i = 1
for tc in range(test_cases):
	n = arr[i]
	i += 1
	cnt = arr[i:i + n]
	i += n
	max_i = cnt.index(max(cnt))
	print(max_i + 1)


import sys
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

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

def mainak(n):
	ts = 0
	for (idx, i) in enumerate(n):
		if i > n[ts]:
			ts = idx
	return ts + 1
t = inp()
for _ in range(t):
	n = int(input().strip())
	nums = [int(x) for x in input().strip().split()]
	print(mainak(nums))


def revisited():
	n = int(input())
	lst_ans = []
	for i in range(n):
		diff_col = int(input())
		cnt = list(map(int, input().split()))
		i = cnt.index(max(cnt)) + 1
		lst_ans.append(i)
	for k in lst_ans:
		print(k)
revisited()


import math
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	maxC = max(c)
	i = c.index(maxC)
	print(i + 1)


def main():
	for t in range(int(input())):
		n = int(input())
		a = [0] + list(map(int, input().split()))
		(pos, mx) = (0, 0)
		for i in range(1, n + 1):
			if a[i] > mx:
				mx = a[i]
				pos = i
		print(pos)
main()


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	_max = -1
	pos = 0
	for i in range(n):
		if arr[i] > _max:
			_max = arr[i]
			pos = i + 1
	print(pos)
test_case = int(input())
for i in range(test_case):
	solve()


def func(n, str):
	str = str.split()
	str = [int(i) for i in str]
	return str.index(max(str))
t = int(input())
for i in range(t):
	n = int(input())
	str = input()
	ans = func(n, str)
	print(ans + 1)


for _ in [0] * int(input()):
	input()
	a = list(map(int, input().split()))
	print(1 + a.index(max(a)))


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	m = l[0]
	ind = 1
	for i in range(1, len(l) + 1):
		if l[i - 1] > m:
			m = l[i - 1]
			ind = i
	print(ind)


for _ in range(int(input())):
	n = int(input())
	cnt = [int(x) for x in input().split()]
	max_idx = -1
	max_cnt = -1
	for i in range(n):
		curr_cnt = cnt[i]
		if curr_cnt > max_cnt:
			max_cnt = curr_cnt
			max_idx = i + 1
	print(max_idx)


t = int(input())
while t:
	n = int(input())
	maxi = -1
	balls = list(map(int, input().split()))
	for i in range(n):
		if balls[i] > maxi:
			maxi = balls[i]
			ans = i + 1
	print(ans)
	t -= 1


t = int(input())
for i in range(t):
	numcolors = input()
	colors = list(map(int, input().split()))
	maxnum = max(colors)
	for i in range(len(colors)):
		if colors[i] == maxnum:
			print(i + 1)
			break

def test():
	colors = [1, 3, 5, 14, 14]
	maxnum = max(colors)
	for i in range(len(colors)):
		if colors[i] == maxnum:
			print(i + 1)
			break


def solution(arr):
	print(arr.index(max(arr)) + 1)
t = int(input())
for _ in range(t):
	n = input()
	arr = list(map(int, input().split(' ')))
	solution(arr)