MKEQUAL - Make them equal !

You have an array containing N elements. At any move, you choose two indices i and j ( 0 <= i, j < N and i != j ) and increment value at one index and decrement value at other index. You can make this move any number of times. What is the maximum number of elements which can have the same value (after any number of moves) ?

Input

First line consists of T, the number of test cases. (1 <= T <= 100)

T sets follow. Each set contains N, the number of elements in the array, in the first line. (1 <= N <= 100000)

Next line of each set consists of N space separated integers (0 <= value <= 100000)

Output

Output T lines each containing the required answer.

Example

Input:
1
4
1 2 3 4

Output: 
3

Added by:Pandian
Date:2013-10-15
Time limit:0.5s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own

hide comments
2017-07-30 15:59:30
Only Pen and Paper can help you !
2017-06-06 08:49:00
Good Implementation of binary search
2017-05-19 20:17:53
No getting the question. Can anybody plz explain me the output?


Last edit: 2017-05-19 20:18:24
2017-05-18 07:02:10
very easy
2017-03-31 17:48:05
Accept in 1 go
2015-06-08 20:33:39 AlphaDecay
Nice Question ! :D
2013-12-14 20:49:06 ABHISHEK004
problem setter should specify the max size of array correctly...with fixed size of 10000 had 2 WA's..size can be more than that

EDIT : Thanks for pointing out. Constraints modified.

Last edit: 2013-12-14 20:49:39
2013-12-14 20:49:06 Rishul Aggarwal
Seems that the test data has some flaw.. two similar solutions were judged differently and two different solutions were accepted
2013-12-14 20:49:06 Jacob Plachta
Fantastic... N can be larger than 10,000 (but no larger than 90,000).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.