有 $$$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$$$)。
输出
对于每个测试用例,输出一行包含答案。
示例
输入复制
311026 741 4 3 4
输出复制
112
注意
在第一个测试用例中,玩家 $$$1$$$ 为每个起始玩家获胜。
在第二个测试用例中,玩家 $$$2$$$ 为每个起始玩家获胜。
在第三个测试用例中,玩家 $$$2$$$ 和 $$$4$$$ 可以获胜。