Monica decides that she would like to get to know the neighbours in the apartment better. She makes a batch of wonderful chocolates and hangs them on the door in a basket hoping that her neighbors will take some and they can meet. The neighbours (including Joey) eventually go crazy over the candy and demand more. Eventually, she keeps a bowl full of chocolates at the door for the last time.

There are N neighbours. The i^{th} neigbhour has initial energy equal to A_{i}. There is one bowl filled with chocolates. The neighbours are made to stand in a row and the bowl is passed around by obeying the following rules:

Any person can hold the bowl initially. 
If the person holding the bowl has positive energy, he/she passes the bowl to the person on the immediate right of him/her. The rightmost person in the row passes the bowl to the leftmost person in the row. 
The act of passing the bowl takes 1 second. 
If the person holding the bowl has non-positive energy, he/she drops the bowl.  
After each pass, the energy of the person reduces by 1. 

Among all possible ways in which the N neighbours start the game, find the maximum time until the bowl is dropped.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- First line of each testcase contains one integer N.
- Second line of each testcase contains of N integers, denoting the elements of array A.

------ Output Format ------ 

For each testcase, output in a single line the maximum time until the bowl is dropped.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A[i] ≤ 10^{6}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
3
2 1 1
3
0 5 0
4
3 0 2 1

----- Sample Output 1 ------ 
4
1
3

----- explanation 1 ------ 
Test case 1: One of the optimal orders in which all the neighbours can stand in the row is:   
$1$ $\rightarrow$ $2$ $\rightarrow$ $3$ $\rightarrow$ $1$. The bowl is initially with person $1$. 
- Person $1$, in one second, passes the bowl to person $2$ and his/her own energy becomes $1$. 
- Person $2$, in one second, passes the bowl to person $3$ and his/her own energy becomes $0$.
- Person $3$, in one second, passes the bowl to person $1$ and his/her own energy becomes $0$.
- Person $1$, in one second, passes the bowl to person $2$ and his/her own energy becomes $0$.
- Person $2$ has $0$ energy, so he/she drops the bowl. 
Thus, the bowl is dropped after $4$ seconds.

Test case 2: One of the optimal orders in which all the neighbours can stand in the row is:   
$2$ $\rightarrow$ $1$ $\rightarrow$ $3$ $\rightarrow$ $2$. The bowl is initially with person $2$. Thus, it would travel as $2$ $\rightarrow$ $1$. The bowl can not be passed further due to $0$ energy of person $1$.

Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	a = a[::-1]
	minn = a[-1]
	minnind = a.index(minn)
	total = n * minn
	total += minnind
	print(total)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	ans = a[-1]
	print(ans * n + a.index(ans))


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = sorted(list(map(int, input().strip().split())), key=lambda x: -x)
	r = 0
	if a[-1] > 0:
		r = a[-1]
	l = n - 2
	while l >= 0 and (a[l] <= 0 or a[l] == a[l + 1]):
		l -= 1
	l += 1
	print(r * n + l)


for _ in range(int(input())):
	N = int(input())
	A = sorted(list(map(int, input().split())), reverse=True)
	sm = N * A[-1]
	x = A[-1]
	for i in range(len(A)):
		if A[i] == x:
			x = i
			break
	sm += i
	print(sm)


for t in range(int(input())):
	n = int(input())
	P = sorted([int(x) for x in input().split(' ')], reverse=True)
	print(n * P[-1] + P.index(P[-1]))


from bisect import bisect_left
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	d = a.count(0)
	if d != 0:
		t = 0
		for i in range(n):
			if a[i] != 0:
				t += 1
			else:
				break
		print(t)
	else:
		s = a[-1]
		d = a.index(s)
		res = s * n + d
		print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	temp = input().split()
	A = [int(ele) for ele in temp]
	Min = min(A)
	MinCount = 0
	for ele in A:
		if ele == Min:
			MinCount += 1
	ans += Min * n
	ans += n - MinCount
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	c = 0
	for i in l:
		if i == 0:
			c += 1
	m = 0
	if c == 0:
		min1 = min(l)
		count_min = 0
		for i in l:
			if i == min1:
				count_min += 1
		m = min1 * n
		m = m + (n - count_min)
	else:
		m = n - c
	print(m)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	a.sort(reverse=True)
	mn = a.index(min(a))
	print(n * min(a) + mn)


t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	if A[0] == 0:
		i = 0
		while A[i] == 0:
			i += 1
			if i == n:
				break
		print(n - i)
	else:
		count = 1
		for i in range(1, n):
			if A[0] == A[i]:
				count += 1
			else:
				break
		ans = (A[0] + 1) * n - count
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	ind = 0
	mini = arr[0]
	for i in range(n):
		if arr[i] < mini:
			mini = arr[i]
			ind = i
	t = n * mini + ind
	print(t)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	a.reverse()
	e = 0
	e += a[-1] * n
	z = a.count(a[-1])
	e += n - z
	print(e)


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	time = 0
	x = 0
	c = 0
	for j in range(len(A) - 1):
		if A[j] != A[j + 1]:
			x = j
			c = 0
			break
		else:
			c = 1
	time = N * A[x]
	if c == 0:
		time += N - x - 1
	print(time)


def main():
	test_cases = int(input())
	for t in range(test_cases):
		n = int(input())
		arr = [int(i) for i in input().split()]
		arr = sorted(arr, reverse=True)
		(ind, mini) = (0, arr[0])
		for i in range(n):
			if arr[i] < mini:
				mini = arr[i]
				ind = i
		ind = ind + 1
		out = mini * n + ind - 1
		print(out)
main()


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	minValue = 1000000
	for j in a:
		minValue = min(minValue, j)
	ans = minValue * n
	for j in a:
		if j > minValue:
			ans += 1
	print(ans)
t = int(input())
for i in range(t):
	solve()


def solve():
	n = int(input())
	li = list(map(int, input().split()))
	li.sort(reverse=True)
	dic = {}
	dic1 = {}
	key = 0
	for i in li:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
		if i in dic1:
			dic1[i] += 1
		else:
			dic1[i] = 1
	for (i, j) in dic.items():
		key = dic1.pop(i)
		dic1[i] = j
	key = li[-1]
	print(n * key + n - dic[key])
t = int(input())
for i in range(t):
	solve()


def solve():
	n = int(input())
	li = list(map(int, input().split()))
	li.sort(reverse=True)
	dic = {}
	for i in li:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	key = list(dic)[-1]
	print(n * key + n - dic[key])
t = int(input())
for i in range(t):
	solve()


T = int(input())
for _ in range(T):
	n = int(input())
	L = list(map(int, input().split()))
	L.sort(reverse=True)
	m = min(L)
	x = L.index(m)
	print(m * n + x)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort(reverse=True)
	x = arr[n - 1]
	if x == 0:
		y = arr.count(0)
		print(n - y)
	else:
		y = arr.count(x)
		r = x * n
		print(r + (n - y))


for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	ar.sort()
	mi = min(ar)
	flag = ar.count(mi)
	ans = mi * n + (n - flag)
	print(ans)


import math
for i in range(int(input())):
	aaa = int(input())
	bbb = input().split()
	for j in range(len(bbb)):
		bbb[j] = math.ceil(max(0, int(bbb[j])))
	smh = min(bbb)
	smhh = []
	for k in range(len(bbb)):
		if bbb[k] == smh:
			smhh.append(k)
	print(len(bbb) - len(smhh) + smh * len(bbb))


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	arr.sort(reverse=True)
	min_value = min(arr)
	for i in range(n):
		arr[i] -= min_value
	j = 0
	while arr[j] > 0:
		j += 1
	print(j + min_value * n)


for _ in range(int(input())):
	x = int(input())
	zoop = list(map(int, input().split()))
	zoop.sort(reverse=True)
	ans = 0
	if zoop[-1] != 0:
		for i in range(zoop[-1]):
			ans += len(zoop)
		i = 0
		mn = min(zoop)
		while zoop[i] != mn:
			ans += 1
			i += 1
	else:
		i = 0
		while zoop[i] != 0:
			ans += 1
			i += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	array = input().split()
	mini = int(array[0])
	count = 0
	for k in range(n):
		val = int(array[k])
		if val == mini:
			count += 1
		elif val < mini:
			mini = val
			count = 1
	print(n - count + n * mini)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	v = [-1] * n
	s = 0
	m = -1
	for j in range(n):
		if m < 0 or m > a[j]:
			m = a[j]
			s = j
	j = s
	ans = n
	for z in a:
		if z == m:
			ans -= 1
	print(ans + m * n)


T = int(input())
for tc in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	v = [-1] * N
	startI = 0
	minValue = -1
	for i in range(N):
		if minValue < 0 or minValue > A[i]:
			minValue = A[i]
			startI = i
	i = startI
	ans = N
	for a in A:
		if a == minValue:
			ans -= 1
	print(ans + minValue * N)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	mn = min(arr)
	ans = mn * n
	for i in range(n):
		arr[i] -= mn
	print(ans + n - arr.count(0))


import random

def s2(n, arr):
	min_ele = min(arr)
	ind = []
	for i in range(n):
		if arr[i] == min_ele:
			ind += [i]
	ans = min_ele * n + n - len(ind)
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(s2(n, arr))


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	mini = min(ar)
	more = 0
	for num in ar:
		if num > mini:
			more += 1
	ans = n * mini + more
	print(ans)


for q in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	lst.sort(reverse=True)
	if lst[-1] == 0:
		index = lst.index(0)
		print(index)
	else:
		index = lst.index(lst[-1])
		ans = index + lst[-1] * n
		print(ans)


t = int(input())
for q in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.sort()
	a.reverse()
	if a[-1] == 0:
		index = a.index(0)
		print(index)
	else:
		index = a.index(a[-1])
		time = index + a[-1] * n
		print(time)


def ans(arr, n):
	x = min(arr)
	z = arr.count(x)
	print(x * n + n - z)
	return
x = int(input())
for i in range(x):
	n = int(input())
	arr = [int(i) for i in input().split()]
	ans(arr, n)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = min(arr)
	print(m * n + n - arr.count(m))


T = int(input())
for i in range(T):
	N = int(input())
	AE = [int(o) for o in input().split(' ')]
	if 0 in AE:
		print(N - AE.count(0))
	else:
		s = sorted(AE, reverse=True)
		l = s[-1]
		print(N * l + N - s.count(l))


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	min_element = min(arr)
	min_count = arr.count(min_element)
	print(min_element * n + (n - min_count))


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	m = min(x)
	c = 0
	for i in range(len(x)):
		if x[i] > m:
			c += 1
	print(n * m + c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mn = min(a)
	print(n * mn + n - a.count(mn))


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	min1 = min(a)
	c = 0
	for i in a:
		if i == min1:
			c = c + 1
	print(n - c + min1 * n)


for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	MIN = min(ar)
	MIN_CNT = ar.count(MIN)
	print(MIN * n + n - MIN_CNT)


def x(l):
	l1 = []
	c = 0
	for j in l:
		if j > 0:
			c = c + 1
	return c
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	time = 0
	c = 0
	for j in l:
		if j == 0:
			c = 1
			break
	if c == l:
		time = x(l)
	else:
		y = min(l)
		time = time + min(l) * len(l)
		for k in range(n):
			l[k] = l[k] - y
		time = time + x(l)
	print(time)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mini = min(arr)
	arr.sort()
	f = 0
	for i in range(n):
		if arr[i] > mini:
			print(n * arr[0] + n - i)
			f = 1
			break
	if not f:
		print(arr[0] * n)


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = min(a)
	c = a.count(m)
	ans = m * n + (n - c)
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	arrA = input().split()
	arrA = [int(i) for i in arrA]
	a = min(arrA)
	b = arrA.count(a)
	print(N * a + (N - b))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	v = min(a)
	c = a.count(v)
	if v:
		print(v * n + n - c)
	else:
		print(n - c)


try:
	t = int(input())
	while t > 0:
		n = int(input())
		nn = 0
		nnn = 0
		nnnn = 0
		l = list(map(int, input().strip().split()))
		l.sort()
		lt = 0
		lt2 = 1
		count_for_zero = 0
		count_for_one = 1
		if l[0] == 0:
			while True and lt < n:
				if l[lt] == 0:
					lt += 1
					count_for_zero += 1
					continue
				break
			print(n - count_for_zero)
			continue
		elif l[0] >= 1:
			while True and lt2 < n:
				if l[0] == l[lt2]:
					lt2 += 1
					count_for_one += 1
					continue
				break
			ans = n * l[0] + n - count_for_one
			print(ans)
			continue
			t = t - 1
except EOFError as e:
	pass


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	cnt = 0
	for i in lst:
		if i == 0:
			cnt += 1
	ans = 0
	if cnt == 0:
		mn = min(lst)
		cmin = 0
		for i in lst:
			if i == mn:
				cmin += 1
		ans = mn * n
		ans = ans + (n - cmin)
	else:
		ans = n - cnt
	print(ans)


t = int(input())
while t != 0:
	n = int(input())
	s = input().split(' ')
	a = []
	mini = 10000007
	for i in range(n):
		ele = int(s[i])
		a.append(ele)
		mini = min(mini, a[i])
	res = n * mini
	for i in range(n):
		if a[i] > mini:
			res = res + 1
	print(res)
	t = t - 1


def Time(arr, n):
	arr.sort(reverse=True)
	time = 0
	lim = n - 1
	for i in range(n - 2, -1, -1):
		if arr[i] == arr[i + 1]:
			lim = i
			continue
		else:
			break
	time = n * arr[lim]
	if time < 0:
		return lim
	time += lim
	return time
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().rstrip().rsplit()))
	print(Time(arr, n))


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			print(p)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	time = 0
	a.sort()
	count = 0
	if a[0] == 0:
		print(n - a.count(0))
	else:
		time = a[0] * n
		for i in range(n):
			if a[i] > a[0]:
				time += 1
		print(time)


t = int(input())
for test in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	arr = arr[::-1]
	time = arr[-1] * n
	for i in arr:
		if i > arr[-1]:
			time += 1
	print(time)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	mn = min(a)
	ans = mn * n
	for i in range(n):
		if a[i] > mn:
			ans += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = min(a)
	c = a.count(k)
	s = (k + 1) * n - c
	print(s)


def check(n, a):
	mn = min(a)
	if mn > 0:
		total = mn * n
		for i in range(n):
			if a[i] - mn > 0:
				total += 1
	else:
		total = 0
		for i in range(n):
			if a[i] > 0:
				total += 1
	return total
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(check(n, a))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = min(a)
	l = []
	c = 0
	for j in range(n):
		if a[j] == k:
			l.append(j)
			c += 1
	s = (k + 1) * n - c
	print(s)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	j = min(l)
	m = (j + 1) * n - l.count(j)
	print(m)


for t in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	lis.sort(reverse=True)
	if n == 1:
		print(0)
	elif min(lis) == max(lis):
		print(lis[0] * n)
	else:
		mini = min(lis)
		for i in range(n):
			lis[i] -= mini
		res = mini * n
		index = lis.index(0)
		res += index
		print(res)


test = int(input())
for i in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	min_elem = min(arr)
	passes = min_elem * n
	for j in range(len(arr)):
		arr[j] -= min_elem
	count = 0
	for k in arr:
		if k > 0:
			count += 1
	print(count + passes)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	cnt = arr[0] * n
	k = arr[0]
	for i in range(n):
		arr[i] = arr[i] - k
	j = n - 1
	while arr[j] != 0:
		cnt += 1
		j -= 1
	print(cnt)


t = int(input())
for j in range(t):
	N = int(input())
	a = list(map(int, input('').strip().split()))[:N]
	a.sort()
	min1 = min(a)
	T = min(a) * N
	a = a[::-1]
	count = a.count(min1)
	T = T + (N - count)
	print(T)


for i in range(0, int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	m = a[-1]
	c = a.count(m)
	rem = n - c
	ans = m * n + rem
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = min(a)
	a = [i - x for i in a]
	c = 0
	for i in range(n):
		if a[i] != 0:
			c += 1
	print(x * n + c)


def _func(n, a):
	if n == 1:
		return '0'
	if 0 not in a:
		a.sort()
		_min = min(a)
		_count = a.count(_min)
		return n * _min + (n - _count)
	else:
		return n - a.count(0)

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		print(_func(n, a))
main()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	p = 0
	m = min(l)
	ans = m * n
	for i in range(n):
		if l[i] > m:
			p = p + 1
	ans = ans + p
	print(ans)


for i in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split(' ')))
	count0 = 0
	mini = min(lis)
	for i in range(len(lis)):
		if lis[i] == 0:
			count0 += 1
	if count0 > 0:
		print(n - count0)
	else:
		mincount = 0
		for i in lis:
			if i == mini:
				mincount += 1
		print(mini * n + (n - mincount))


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().strip().split()))
	min_ = min(arr)
	for i in range(n):
		arr[i] -= min_
	count_zero = 0
	for i in range(n):
		if arr[i] == 0:
			count_zero += 1
	ans = (min_ + 1) * n - count_zero
	print(ans)
	t -= 1


def orican(N, A):
	A.sort()
	i = A[0]
	count = N * i
	for i in A:
		if i > A[0]:
			count += 1
	return count
t = int(input())
for _ in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	result = orican(N, A)
	print(result)


t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	cnt = arr.count(arr[-1])
	print(arr[-1] * n + n - cnt)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = min(a)
	cnm = a.count(m)
	c0 = a.count(0)
	if c0 == 0:
		a = m * n
		print(a + (n - cnm))
	else:
		print(n - c0)


t = int(input())
a = []
for i in range(2 * t):
	a += [list(map(int, input().split()))]

def f(n):
	n.sort()
	l = [x for x in n if x == n[0]]
	return len(n) - len(l) + len(n) * n[0]
for i in range(t):
	print(f(a[2 * i + 1]))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(min(arr) * n + n - arr.count(min(arr)))


for _ in range(int(input())):
	n = int(input())
	b = input().split()
	b.sort(reverse=True)
	m = min(b)
	i = b.index(m)
	print(int(m) * n + i)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	sorted(arr, reverse=True)
	m = min(arr)
	t = 0
	for i in arr:
		if i > m:
			t += 1
	print(m * n + t)


t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(list(map(int, input().split())), reverse=True)
	idx = min(a)
	c = 0
	for i in range(0, n):
		a[i] = a[i] - idx
	for i in a:
		if i != 0:
			c += 1
	print(f'{n * idx + c}')


t = int(input())
for tc in range(0, t):
	n = int(input())
	arr = list(map(int, input().split()))
	min = arr[0]
	ct = 1
	for i in range(1, n):
		if arr[i] < min:
			min = arr[i]
			ct = 1
		elif arr[i] == min:
			ct += 1
	val = min * n + n - ct
	print(val)


t = int(input())
for test in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	l = l[::-1]
	a = l[-1]
	b = l.index(a)
	print(n * a + b)


from collections import Counter
from math import ceil, floor, log
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())
for _ in range(int(input())):
	n = inp_int()
	a = inp_lis()
	x = dict(Counter(a))
	a.sort(reverse=True)
	if 0 in a:
		print(a.index(0))
		continue
	m = a[-1]
	c = m * n
	c += a.index(m)
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, list(input().split())))
	l = sorted(l)[::-1]
	mi = l[-1]
	for i in range(n):
		l[i] = l[i] - mi
	count = 0
	for i in l:
		if i > 0:
			count = count + 1
	print(n * mi + count)