Chef is the new king of the country Chefland. As first and most important responsibility he wants to reconstruct the road system of Chefland. There are N (1 to N) cities in the country and each city i has a population Pi. Chef wants to build some bi-directional roads connecting different cities such that each city is connected to every other city (by a direct road or through some other intermediate city) and starting from any city one can visit every other city in the country through these roads. Cost of building a road between two cities u and v is Pu x Pv. Cost to build the road system is the sum of cost of every individual road that would be built. 
Help king Chef to find the minimum cost to build the new road system in Chefland such that every city is connected to each other.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. 
First line contains an integer N denoting the number of cities in the country. Second line contains N space separated integers Pi, the population of i-th city.

-----Output-----
For each test case, print a single integer, the minimum cost to build the new road system on separate line.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ Pi ≤ 106

-----Example-----
Input:
2
2
5 10
4
15 10 7 13

Output:
50
266

Difficulty: interview

Starter code:

Solutions:
t=int(input())
for _ in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 a.sort()
 s=sum(a)
 if a[0]*(s-a[0])<=a[n-1]*(s-a[n-1]):
  print(a[0]*(s-a[0]))
 else:
  print(a[n-1]*(s-a[n-1]))

def solve(A,n):
 
 
 
 A.sort()
 res = 0
 for i in range(1,n):
  
  res = res + A[i]*A[0]
  
 return res
 
 
t = int(input())

for _ in range(t):
 
 n = int(input())
 
 A=list(map(int,input().split()))
 print(solve(A,n))

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 m=1000001
 s=0
 for x in map(int,input().split()):
  m=min(m,x)
  s+=x
 s-=m
 s*=m
 print(s)

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 m=1000001
 l=[]
 for x in map(int,input().split()):
  l.append(x)
  m=min(m,x)
 s=0
 for i in l:
  s+=m*i
 s-=m*m
 print(s)

# cook your dish here
t=0
try:
 t=int(input())
except:
 pass

for _ in range(t):
 
 n= int(input())
 p=list(map(int, input().split()))
 
 middle = min(p)
 p.remove(middle)
 cost =0
 for i in p:
  cost+= i*middle
 print(cost)

for _ in range(int(input())):
 n=int(input())
 ar=[int(x) for x in input().split()]
 if n==1:
  print(ar[0])
 elif n==2:
  print(ar[0]*ar[1])
 else:
  ar.sort()
  an=0
  for i in range(1,n):
   an+=ar[0]*ar[i]
  print(an)


t=int(input()) 
for kk in range(t): 
 n=int(eval(input ())) 
 a=[int(x) for x in input ().split()] 
 k=min(a) 
 s=0
 for i in range(n): 
  if a[i]!=k:  
   s+=k*a[i] 
 print(s)
   
 
 
 
  
  

  
  
 
 
    
  
  
   
   
  
  

  
 
 
 

 


T = int(input())
ans = []

for _ in range(T):
 N = int(input())
 P = [int(i) for i in input().split()]

 m = min(P)
 ans.append((sum(P)-m)*m)

for i in ans:
 print(i)



# cook your dish here
t=int(input())
for _ in range(t):
 n=int(input())
 arr=[int(i) for i in input().split()]
 min_val=1000000
 for ele in arr:
  if min_val>ele:
   min_val=ele
 tot=0
 for ele in arr:
  if ele!=min_val:
   tot+=ele
 print(min_val*tot)
  
 


for _ in range(int(input())):
 c = int(input())
 p = list(map(int,input().split()))
 p.sort()
 count = 0
 for i in range(1,c):
  count+=p[0]*p[i]
 print(count)


# cook your dish here
t=int(input())

def kingship(p,n):
 
 s=0
 m=min(p)
 
 for i in range(0,n):
  s+=p[i]*m
 return s-m*m
for _ in range(t):
 n=int(input())
 p=list(map(int,input().split()))
 
 r=kingship(p,n)
 print(r)

# cook your dish here
t=int(input())

def kingship(p,n):
 
 s=0
 p=sorted(p)
 
 for i in range(1,n):
  s+=p[0]*p[i]
 return s
for _ in range(t):
 n=int(input())
 p=list(map(int,input().split()))
 
 r=kingship(p,n)
 print(r)

try:
 t=int(input())
 for i in range(t):
  n=int(input())
  l=list(map(int,input().split()))
  l.sort()
  cost=0
  for j in range(1,len(l)):
   cost=cost+l[0]*l[j]
  print(cost)
except:
 pass

# cook your dish here
t = int(input())
for _ in range(t):
 n = int(input())
 arr = list(map(int, input().split()))
 arr.sort()
 ans = 0
 for i in range(1,n):
  ans = ans + arr[0]*arr[i]
 print(ans)


t=int(input())
for i in range(t):
 n=int(input())
 a=list(map(int, input().split()))
 a.sort()
 s=0
 for j in range(1,n):
  s+=a[j]*a[0]
 print(s)


for _ in range(int(input())):
 n = int(input())
 ls = list(map(int,input().split()))
 ls.sort()
 s =0
 for i in range(1,n):
  s+= ls[i]*ls[0]
 print(s)

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 x=min(l)
 y=0
 for i in l:
   y+=i*x 
 print(y-x*x)


# cook your dish here
for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 x=min(l)
 y=0
 for i in l:
  if i!=x:
   y+=i*x 
 print(y)


for _ in range(int(input())):
 N=int(input())
 arr=list(map(int,input().split()))
 arr.sort()
 sum=0
 for i in range(1,len(arr)):
  sum+=arr[i]*arr[0]
 print(sum)

# cook your dish here
for t in range(int(input())):
 n = int(input())
 p = list(map(int, input().split()))
 m = min(p)
 s = 0
 for i in p:
  if i != m:
   s += i*m
 print(s)

# cook your dish here
for i in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 l.sort()
 sum=0
 for j in range(1,len(l)):
  sum+=l[j]
 print(sum*l[0])

for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 l.sort()
 s=sum(l[1:])
 print(l[0]*s)