Chef and Game with Sequence

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef has a sequence A containing N integers A_{1}, A_{2}, ..., A_{N}.
Chef is playing a game with this sequence. In this game, he may perform the following operation any number of times (including zero): Choose an arbitrary pair of elements from the sequence such that their sum is even, delete these two elements from the sequence and insert their sum into the sequence instead.
The goal of the game is to minimise the number of elements in the sequence.
Help Chef to play the game and find the minimum possible size of the sequence at the end of the game!
Input
 The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains a single integer N.
 The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N}.
Output
For each test case, print a single line containing one integer — the minimum possible final size of the sequence.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N ≤ 100
 1 ≤ A_{i} ≤ 1,000 for each valid i
Subtasks
Subtask #1 (100 points): original constraints
Example
Input: 2 2 1 2 5 7 4 3 2 6 Output: 2 1
Example
Example case 1: There is no pair of elements with an even sum. Thus, the sequence must remain the same and the answer is 2.
Example case 2: Chef can choose elements 7 and 3 in the first step, delete them and insert 10 in the sequence. Now all its elements are even and Chef can choose any two elements on each of the following steps of the game until the sequence contains only one element.
Author:  kefaa 
Tester:  mgch 
Editorial  https://discuss.codechef.com/problems/L56GAME 
Tags  cakewalk, kefaa, ltime56, taran_1407 
Date Added:  16012018 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 