Migrated from Lutece 3030 Chisato想要赢

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

猜拳输给了 $Takina$ 后，$Chisato$ 感到很不服气。

于是 $Chisato$ 想出了一个新游戏准备和 $Takina$ 玩。

游戏开始时，桌面上放有 $n$ 个杯子，第 $i$ 个杯子中有 $a_i$ 单位的水。

$Chisato$ 和 $Takina$ 轮流进行操作（$Chisato$ 先手）。对于一次操作，可以选择下面的一项执行：

1、选择其中一个有水的杯子倒掉 $1$ 单位的水。 2、选择其中两个有水的杯子，把一个杯子里的水全部倒入另一个杯子中。

无法进行操作者输掉游戏。

$Chisato$ 和 $Takina$ 都很聪明，所以她们会采用最优策略进行游戏。

同时，为了排除运气的影响，充分体现个人实力，她们一共将进行 $T$ 轮游戏。

现在 $Chisato$ 想知道，$T$ 轮游戏中她能赢几轮呢？

Input

第一行一个整数 $T$ $(1 \le T \le 10^{4})$，代表游戏轮数。 接下来给出每轮游戏的初始条件。对于每轮游戏： 第一行一个整数 $n$ $(1 \le n \le 50)$，代表水杯的数量。 第二行 $n$ 个整数，分别代表每个水杯的初始水量 $a_i$ $(1 \le a_i \le 10^{3})$。

Output

一行一个整数，代表 $T$ 轮游戏中 $Chisato$ 的获胜轮数。

Samples

2
1
3
2
1 2

2

Constraints

$1 \le T \le 10^{4}$，$1 \le n \le 50$，$1 \le a_i \le 10^{3}$

Resources

2023 UESTC ICPC Training for Math