← 返回题目列表

Codeforces · 2200/A

A. 吃游戏

中文机器翻译题面 查看原题

有 $$$n$$$ 名玩家在圆桌旁玩游戏。第 $$$i$$$ 个玩家有 $$$a_i$$$ 菜可吃。他们轮流吃食物,任何玩家都可以先吃。

在他们的回合中,如果玩家 $$$i$$$ 有剩余的菜肴,他们必须吃完一道菜。然后,玩家 $$$(i \bmod n) + 1$$$ 开始轮到他们。这样一直持续到所有菜肴都吃完为止。

吃完最后一道菜的玩家被视为获胜者。确定可能成为获胜者的玩家人数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5000$$$),测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10$$$)。

每个测试用例的第二行包含 $$$n$$$ 个整数,即 $$$a$$$ 的元素 ($$$1 \leq a_i \leq 10$$$)。

输出

对于每个测试用例,输出一行包含答案。

示例

输入
复制

3
1
10
2
6 7
4
1 4 3 4

输出
复制

1
1
2

注意

在第一个测试用例中,玩家 $$$1$$$ 为每个起始玩家获胜。

在第二个测试用例中,玩家 $$$2$$$ 为每个起始玩家获胜。

在第三个测试用例中,玩家 $$$2$$$ 和 $$$4$$$ 可以获胜。