qcjj的蝴蝶结1
题号:NC219720
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

众所周知,qcjj是一个可爱的小姐姐,而可爱的小姐姐都喜欢蝴蝶结。
qcjj有n种不同款式的蝴蝶结,每种款式颜色大小均相同,每种a[i]个,qcjj想知道:
自己还需要买多少个蝴蝶结,才能保证自己可以把这些蝴蝶结分成一模一样的两份,自己留一份,送一份给可爱的室友?

输入描述:

第一行读入一个整数T,表示测试数据的组数。
每组测试数据有两行:
第一行为一个整数n,表示蝴蝶结的款式数,
第二行为n个空格隔开的整数,为每个款式蝴蝶结的个数。

输出描述:

对于每一组测试数据输出一行一个整数,表示qcjj还需要买多少个蝴蝶结。
示例1

输入

复制
1
1
3

输出

复制
1

说明

n \leq 10^5, 保证所有输入都在int范围内。