You are both a shop keeper and a shop assistant at a small nearby shop. You have $n$ goods, the $i$-th good costs $a_i$ coins.

You got tired of remembering the price of each product when customers ask for it, thus you decided to simplify your life. More precisely you decided to set the same price for all $n$ goods you have.

However, you don't want to lose any money so you want to choose the price in such a way that the sum of new prices is not less than the sum of the initial prices. It means that if you sell all $n$ goods for the new price, you will receive at least the same (or greater) amount of money as if you sell them for their initial prices.

On the other hand, you don't want to lose customers because of big prices so among all prices you can choose you need to choose the minimum one.

So you need to find the minimum possible equal price of all $n$ goods so if you sell them for this price, you will receive at least the same (or greater) amount of money as if you sell them for their initial prices.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 100$) — the number of queries. Then $q$ queries follow.

The first line of the query contains one integer $n$ ($1 \le n \le 100)$ — the number of goods. The second line of the query contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^7$), where $a_i$ is the price of the $i$-th good.


-----Output-----

For each query, print the answer for it — the minimum possible equal price of all $n$ goods so if you sell them for this price, you will receive at least the same (or greater) amount of money as if you sell them for their initial prices.


-----Example-----
Input
3
5
1 2 3 4 5
3
1 2 2
4
1 1 1 1

Output
3
2
1
[{"code": "for _ in range(int(input())):\n    n = int(input())\n    A = list(map(int, input().split()))\n    s = sum(A)\n    print((s + n - 1) // n)", "passed": true, "time": 0.15, "memory": 14236.0, "status": "done"}, {"code": "import math\nimport itertools\nimport collections\n\ndef getdict(n):\n    d = {}\n    if type(n) is list or type(n) is str:\n        for i in n:\n            if i in d:\n                d[i] += 1\n            else:\n                d[i] = 1\n    else:\n        for i in range(n):\n            t = ii()\n            if t in d:\n                d[t] += 1\n            else:\n                d[t] = 1\n    return d\ndef cdiv(n, k): return n // k + (n % k != 0)\ndef ii(): return int(input())\ndef mi(): return map(int, input().split())\ndef li(): return list(map(int, input().split()))\ndef lcm(a, b): return abs(a*b) // math.gcd(a, b)\ndef wr(arr): return ''.join(map(str, arr))\ndef revn(n): return int(str(n)[::-1])\ndef prime(n):\n    if n == 2:\n        return True\n    if n % 2 == 0 or n <= 1:\n        return False\n    sqr = int(math.sqrt(n)) + 1\n    for d in range(3, sqr, 2):\n        if n % d == 0:\n            return False\n    return True\n\nq = ii()\nfor i in range(q):\n    n = ii()\n    a = li()\n    print(math.ceil(sum(a)/n))", "passed": true, "time": 0.14, "memory": 14352.0, "status": "done"}, {"code": "# Contest: Codeforces Round #590 (Div. 3) (https://codeforces.com/contest/1234)\n# Problem: A: Equalize Prices Again (https://codeforces.com/contest/1234/problem/A)\n\ndef rint():\n    return int(input())\n\n\ndef rints():\n    return list(map(int, input().split()))\n\n\nq = rint()\nfor _ in range(q):\n    n = rint()\n    a = rints()\n    print((sum(a) + n - 1) // n)\n", "passed": true, "time": 0.15, "memory": 14240.0, "status": "done"}, {"code": "#JMD\n#Nagendra Jha-4096\n\n \nimport sys\nimport math\n\n#import fractions\n#import numpy\n \n###File Operations###\nfileoperation=0\nif(fileoperation):\n    orig_stdout = sys.stdout\n    orig_stdin = sys.stdin\n    inputfile = open('W:/Competitive Programming/input.txt', 'r')\n    outputfile = open('W:/Competitive Programming/output.txt', 'w')\n    sys.stdin = inputfile\n    sys.stdout = outputfile\n\n###Defines...###\nmod=1000000007\n \n###FUF's...###\ndef nospace(l):\n    ans=''.join(str(i) for i in l)\n    return ans\n \n \n \n##### Main ####\nt=int(input())\nfor tt in range(t):\n    n=int(input())\n    #n,k,s= map(int, sys.stdin.readline().split(' '))\n    a=list(map(int,sys.stdin.readline().split(' ')))\n    s=sum(a)\n    v=(s//n)\n    if(v*n<s):\n        v+=1\n    print(v)\n    \n    \n#####File Operations#####\nif(fileoperation):\n    sys.stdout = orig_stdout\n    sys.stdin = orig_stdin\n    inputfile.close()\n    outputfile.close()", "passed": true, "time": 0.14, "memory": 14092.0, "status": "done"}, {"code": "def ii(): return int(input())\ndef fi(): return float(input())\ndef si(): return input()\ndef mi(): return map(int,input().split())\ndef li(): return list(mi())\n\nimport math\n\nq=ii()\nfor i in range(q):\n    n=ii()\n    a=li()\n    s=sum(a)\n    ans=math.ceil(s/n)\n    print(ans)", "passed": true, "time": 0.14, "memory": 14092.0, "status": "done"}, {"code": "import math\nq = int(input())\nfor i in range(q):\n\tn = int(input())\n\ts = sum(map(int, input().split()))\n\tprint(int(math.ceil(s / n)))\n\t\n", "passed": true, "time": 0.24, "memory": 14216.0, "status": "done"}, {"code": "import math\n\nq = int(input())\n\nfor _ in range(q):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\n\ts = sum(a)\n\n\tr = s/len(a)\n\tr = math.ceil(r)\n\n\tprint(r)", "passed": true, "time": 0.24, "memory": 14312.0, "status": "done"}, {"code": "a = int(input())\nfor i in range(a):\n    b = int(input())\n    l = list(map(int, input().split()))\n    print((sum(l)+b-1)//b)", "passed": true, "time": 0.14, "memory": 14116.0, "status": "done"}, {"code": "q = int(input())\nfor i in range(q):\n    n = int(input())\n    a = list(map(int, input().split()))\n    print((sum(a) + n - 1) // n)\n", "passed": true, "time": 0.14, "memory": 14108.0, "status": "done"}, {"code": "import math\nq=int(input())\nfor i  in range(q):\n    n=int(input())\n    a=[int(x) for x in input().split()]\n    print(math.ceil(sum(a)/n))\n", "passed": true, "time": 0.14, "memory": 14108.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n = int(input())\n    li = list(map(int, input().split()))\n    print((sum(li) + n - 1) // n)", "passed": true, "time": 0.14, "memory": 14248.0, "status": "done"}, {"code": "#\n# Yet I'm feeling like\n# \tThere is no better place than right by your side\n# \t\tI had a little taste\n# \t\t\tAnd I'll only spoil the party anyway\n# \t\t\t\t'Cause all the girls are looking fine\n# \t\t\t\t\tBut you're the only one on my mind\n\nimport sys\n# import re\ninf = float(\"inf\")\n# sys.setrecursionlimit(1000000)\n\n# abc='abcdefghijklmnopqrstuvwxyz'\n# abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}\nmod,MOD=1000000007,998244353\n# vow=['a','e','i','o','u']\n# dx,dy=[-1,1,0,0,-1,1,-1,1],[0,0,1,-1,1,1,-1,-1]\n\n# from functools import reduce\n# from collections import deque, Counter, OrderedDict,defaultdict\n# from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace\nfrom math import ceil,floor,log,sqrt,factorial,pow,pi,gcd,log10,atan,tan\n# from bisect import bisect_left,bisect_right,insort_left\n# import numpy as np\n# import queue\n# from copy import deepcopy\n# import random\n# import operator\n\ndef get_array(): return list(map(int, sys.stdin.readline().strip().split()))\ndef get_ints(): return map(int, sys.stdin.readline().strip().split())\ndef input(): return sys.stdin.readline().strip()\n\nT=int(input())\nwhile T:\n    n=int(input())\n    Arr=get_array()\n    s=sum(Arr)\n    ans = ceil(s/n)\n    print(ans)\n    T-=1", "passed": true, "time": 0.14, "memory": 14400.0, "status": "done"}, {"code": "# import sys\n# sys.stdin = open(\"in.txt\", \"r\")\n\nt = int(input())\n\nfor i in range(t):\n    n = int(input())\n    arr = [ int(x) for x in input().split() ]\n    s = sum(arr)\n    avg = s // n\n    if avg * n < s: avg += 1\n    print(avg)", "passed": true, "time": 0.14, "memory": 14228.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\n\nq=int(input())\n\nfor testcases in range(q):\n    n=int(input())\n    A=list(map(int,input().split()))\n\n    print(-(-sum(A)//n))\n", "passed": true, "time": 0.2, "memory": 14356.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n = int(input())\n    a = sum(list(map(int, input().split())))\n\n    print((a+n-1)//n)\n", "passed": true, "time": 0.14, "memory": 14120.0, "status": "done"}, {"code": "import math\nn = int(input())\nfor i in range(n):\n    k = int(input())\n    a = [int(i) for i in input().split()]\n    print(math.ceil(sum(a) / k))", "passed": true, "time": 0.15, "memory": 14264.0, "status": "done"}, {"code": "import math\nfor i in range(int(input())):\n    n = int(input())\n    t = list(map(int, input().split()))\n    print(math.ceil(sum(t)/n))", "passed": true, "time": 0.24, "memory": 14272.0, "status": "done"}, {"code": "\nq = int(input())\nfor _ in range(q):\n\n    n = int(input())\n    a = [int(x) for x in input().split()]\n    print((sum(a)+n-1)//n)\n\n", "passed": true, "time": 0.23, "memory": 14168.0, "status": "done"}, {"code": "def mp():\n    return map(int, input().split())\n\nq = int(input())\nfor qq in range(q):\n    n = int(input())\n    a = list(mp())\n    s = sum(a)\n    print((s + n - 1) // n)", "passed": true, "time": 0.14, "memory": 14228.0, "status": "done"}, {"code": "q = int(input())\nfor i in range(q):\n    n = int(input())\n    prices_sum = sum(list(map(int, input().split())))\n    print(prices_sum // n + bool(prices_sum % n))\n", "passed": true, "time": 0.14, "memory": 14172.0, "status": "done"}, {"code": "for c in range(int(input())) :\n    n = int(input())\n    a = list(map(int, input().split()))\n    tot = sum(a)\n    print( (tot + n - 1) // n )\n", "passed": true, "time": 0.14, "memory": 14208.0, "status": "done"}, {"code": "from math import ceil\n\nfor i in range(int(input())):\n    n = int(input())\n    ar = list(map(int, input().split()))\n    x = sum(ar)\n    if x % len(ar) == 0:\n        print(x // len(ar))\n    else:\n        print(ceil(x / len(ar)))\n", "passed": true, "time": 0.14, "memory": 14336.0, "status": "done"}, {"code": "import io, sys, atexit, os\nimport math as ma\nfrom decimal import Decimal as dec\nfrom itertools import permutations\nfrom itertools import combinations\n\n\ndef li ():\n\treturn list (map (int, sys.stdin.readline ().split ()))\n\n\ndef num ():\n\treturn map (int, sys.stdin.readline ().split ())\n\n\ndef nu ():\n\treturn int (input ())\n\n\ndef find_gcd ( x, y ):\n\twhile (y):\n\t\tx, y = y, x % y\n\treturn x\n\n\ndef lcm ( x, y ):\n\tgg = find_gcd (x, y)\n\treturn (x * y // gg)\n\n\n\n\n\n\nmm = 1000000007\n\ndef solve ():\n\tt = nu()\n\tfor tt in range (t):\n\t\tn=nu()\n\t\ta=li()\n\t\ts=sum(a)\n\t\tprint(int(ma.ceil(s/n)))\n\n\n\n\n\n\n\n\n\n\n\n\n\ndef __starting_point():\n\tsolve ()\n__starting_point()", "passed": true, "time": 0.14, "memory": 14088.0, "status": "done"}]