一次练习中包含多组互不相关的数据。对于每组数据，小婷老师给出 $N$ 个正整数 $A_1,A_2,\ldots,A_N$，小泽需要统计其中有多少个奇数。

输入文件最先给出测试组数 $T$。请按照输入顺序分别完成每一组统计，并把每组的答案单独输出一行。

输入格式

第一行包含整数 $T$。随后依次给出 $T$ 组数据。每组数据的第一行包含整数 $N$，第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出 $T$ 行，第 $i$ 行表示第 $i$ 组数据中奇数的个数。

4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000

2
1
5
0

2
5
2 4 6 8 10
4
1 3 5 7

0
4

1
6
1 2 3 4 5 6

3

数据范围

• $1\le T\le100$
• $1\le N\le100$
• $1\le A_i\le10^9$