Chef and Destruction

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Arrays have fallen out of Chef's good books, and he plans to destroy all arrays he possesses. He is left with the last array A, consisting of N positive integers. In order to destroy the array, he can perform the following 2 types of operations any number of times.
 Choose any 2 elements, say X and Y, from the given array A such that X != Y, and remove them, or
 Choose any 1 element, say X, from A, and remove it.
In order to destroy the array as quickly as possible, Chef is interested in knowing the minimum number of operations required to destroy it. Please help him achieve this task.
Input
The first line of input contains a single integer T denoting the number of test cases. First line of each test case contains a single integer N — the number of integers in the array A.
Second line of each test case contains N space separated integers denoting the array A.
Output
For each test case, output the required answer in a new line.
Constraints
 1 ≤ T ≤ 50000
 1 ≤ N ≤ 50000
 1 ≤ A_{i} ≤ 10^{9}
 sum of N over all test cases does not exceed 5 × 10^{5}
Example
Input 3 2 1 2 2 1 1 3 1 2 3 Output 1 2 2
Explanation
 Test 1: In an operation, Chef can choose 2 elements X and Y such that X = 1 and Y = 2 and can destroy them as X != Y.
 Test 2: Chef cannot choose 2 elements X and Y such that X != Y. So, he has to use the second operation twice in order to destroy the array.
Author:  ma5termind 
Tester:  antoniuk1 
Editorial  http://discuss.codechef.com/problems/DESTROY 
Tags  cook66, easy, greedy, ma5termind 
Date Added:  2112015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, 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. 