众所周知,qcjj是一个可爱的小姐姐,而可爱的小姐姐都喜欢蝴蝶结。
qcjj有n种不同款式的蝴蝶结,每种款式颜色大小均相同,每种a[i]个,qcjj想知道:
自己还需要买多少个蝴蝶结,才能保证自己可以把这些蝴蝶结分成一模一样的两份,自己留一份,送一份给可爱的室友?
输入描述:
第一行读入一个整数T,表示测试数据的组数。
每组测试数据有两行:
第一行为一个整数n,表示蝴蝶结的款式数,
第二行为n个空格隔开的整数,为每个款式蝴蝶结的个数。
输出描述:
对于每一组测试数据输出一行一个整数,表示qcjj还需要买多少个蝴蝶结。
示例1
说明
, 保证所有输入都在int范围内。