题目描述

有 $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$）。

输出格式

对于每组测试数据，输出一行答案。

说明/提示

在第一个测试用例中，无论哪位玩家先手，第 1 号玩家都会获胜。

在第二个测试用例中，无论哪位玩家先手，第 2 号玩家都会获胜。

在第三个测试用例中，第 2 号和第 4 号玩家都可能获胜。

由 ChatGPT 5 翻译

样例

3
1
10
2
6 7
4
1 4 3 4

1
1
2