Colored Balls: Revisited

Description:

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.

Sample Input:

3
3
1 1 1
1
9
2
4 7

Sample 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.