题目描述

AHUACM 实验室在近几年的 ACM 大赛中屡获佳绩。kunkun 幸运地加入了 AHUACM 实验室，并结识了愿意给他抱大腿的两个队友 xl 和 hhs，他们在暑假集训中获得了比较满意的进步，可是令 xl 和 hhs 比较困扰的是 kunkun 的 cf rating 一直停滞不前，所以他们要惩罚 kunkun 表演《小丑扔球》。

已知 kunkun 要扔 $n$ 种颜色的球，颜色标号从 $1$ 到 $n$，并且第 $i\ (1 \le i \le n)$ 种颜色的球有 ${cnt_i}$ 个。

现在 kunkun 可以对球进行以下操作：

• 在一次操作中，选出两个颜色不同的小球，并丢掉它们。

kunkun 需要一直操作到不能操作为止，即只剩一种颜色的球存在，或者球恰好全部都被丢完。

kunkun 有很多丢球的方案。邪恶的 hhs 和 xl 要求 kunkun 求出在所有的方案中，有多少种颜色的球可能被留到最后，可是 kunkun 太笨了，并不知道怎么算。

作为 ikun 的你，请帮助伟大的 kunkun 算出通过不同的拿球策略，有多少种球能被留到最后。

输入格式

第一行 输入测试用例的组数 $T (1 \le T \le 1000)$。

对于每组数据，第一行包含一个整数 $N$，代表共有 $N (1 \le N \le 10^5)$ 种颜色的小球；

第二行包含 $N$ 个整数 ${cnt_1}, {cnt_2}, {cnt_3},...,{cnt_n}$ $(1\le {cnt_i} \le 10^8)$。

保证所有测试用例中 $N$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数，代表有多少种不同颜色的球能被留到最后。

2
3
3 4 4
4
1 1 2 2

3
2