C. SYPUCPC Problemsetting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's no secret that coming up with a balanced problemset for the SYPUCPC is really hard so the problemsetters needs your help!!

The current problemset has $$$N$$$ problems, Problem with index $$$i$$$ has difficulty of $$$A_i$$$.

We define the overall difficulty of the problemset by the average difficulty of all problems in that problemset, more formally the overall dificulty can be calculated as: $$$\frac{\sum_{i=1}^{i=M}B_i}{M}$$$ where $$$M$$$ is the number of problems in the problemset and $$$B_i$$$ is the difficulty of the $$$i_{th}$$$ problem.

Your task is to remove some (possibly none) problems from the given problemset to acheive the minimum possible overall difficulty.

Note: A problemset must at least have one problem, which means you can't just remove every single problem and call it a day.

Input

The first line of input contains one integer $$$T$$$ ($$$1 \le T \le 10^5$$$) denoting the number of testcases.

The first line of each testcase contains one integer $$$N$$$ ($$$1 \le N \le 10^5$$$)

The second line of each testcase contains $$$N$$$ space-seperated integers $$$A_1,A_2,...,A_N$$$ ($$$800 \le A_i \le 4000$$$)

Its guaranteed that the sum of $$$N$$$ over all testcases is less than or equal to $$$10^5$$$.

Output

Print the minimum overall difficulty you can obtain after removing some problems

Example
Input
2
2
4000 800
3
969 969 969
Output
800
969