Maximum Items with Even Sum

You are given several test cases. For each test case, you are given the number of items and a list of their prices. Your task is to determine the maximum number of items you can purchase such that the sum of the prices is even.

Explanation: A sum is even if and only if the count of odd numbers is even. Thus, if the number of odd-priced items is odd, you must drop exactly one odd-priced item to obtain an even sum. Otherwise, you can take all items.

Example: For the list [1, 2, 3, 4, 5], there are three odd numbers (1, 3, 5). Since three is odd, the maximum number of items you can take is 5 - 1 = 4.

inputFormat

The input is given via standard input (stdin). The first line contains an integer T, the number of test cases. Each test case consists of two lines. The first line contains an integer N, the number of items. The second line contains N space-separated integers representing the prices of the items.

outputFormat

For each test case, output a single integer on a new line via standard output (stdout), representing the maximum number of items that can be purchased such that the sum of prices is even.## sample

2
5
1 2 3 4 5
3
2 4 6

4
3