Shivam is working on electric circuits. He requires some connecting wires. He needs to make a total of N connections and he has mentioned his wire length requirements for each connection in an integer sequence A. For buying wires, he need to decide the length of each wire piece, and he’ll get as many wire pieces of the chosen length each at unit cost (cost 1 per piece) but he can't get wires of different lengths. Also, he can't cut wire pieces to make new pieces of different (smaller) length(s).
But he can connect any number of wires together to form a new single wire piece whose length is the sum of lengths of the wires connected. So, Shivam needs to choose an integer length for buying wires. Shivam hates to waste anything, and he hates it even more if that thing is money.
Shivam is weak in mathematics and is asking you to help him in this situation. Help him decide the length of wires and total number of wires so as to minimize the total expenditure.
Note: You cannot make a connection which requires a wire piece of length X with a wire piece of length Y if X≠Y.
Input:
·        The first line of the input contains T = Number of Test cases
·        The first line of each test case contains an integer N
·        The second line contains N space separated integers A1, A2, …., AN.
Output:
For each test case print a single line containing two space separated integers, length of each wire and the corresponding minimum cost.
Constraints:
·       1 <= T <= 10
·       1 <= N <= 10^5
·        1 <= Ai <= 10^5, for each valid i
Sample Input:
1
3
2 4 8
Sample Output:
2 7

Difficulty: interview

Starter code:

Solutions:
from sys import stdin,stdout
from math import gcd
nmbr=lambda:int(stdin.readline())
lst=lambda:list(map(int, stdin.readline().split()))

for _ in range(nmbr()):
 n=nmbr()
 a=lst()
 g=a[0]
 ans=0
 for v in a[1:]:
  g=gcd(v,g)
 for i in a:
  ans+=i//g
 print(g,ans)

import math
import copy
from functools import reduce

t = int(input())

for i in range(t):
 n = input()
 nums = list(map(int, input().split()))
 n = copy.deepcopy(nums)
 gc = reduce(lambda x,y: math.gcd(x,y),n)
 cost = sum([x//gc for x in nums])
 print(gc,cost)
 


# cook your dish here
def factors(n):
 res=[]
 for i in range (n//2,0,-1):
  if (n%i==0):
   res.append(i)
 return res

def wires(w):
 w.sort()
 a=w[0]
 cost=0
 for num in w:
  if (num%a!=0):
   fact=factors(a)
   break
  cost=cost+(num//a)
 else:
  print(a,cost)
  return None
 for char in fact:
  cost=0
  for num in w:
   if (num%char!=0):
    break
   cost=cost+(num//char)
  else:
   print(char,cost)
   return None
 
t=int(input())
for _ in range (t):
 n=int(input())
 w=[int(x) for x in input().split()]
 wires(w)

# cook your dish here
try:
 import math as m
 for _ in range(int(input())):
  n=int(input())
  a=[int(i) for i in input().split()]
  if n==1:
   print(a[0],1)
   continue
  g=m.gcd(a[0],a[1])
  for i in range(2,n):
   g=m.gcd(g,a[i])
  s=0
  for i in a:
   s+=i//g 
  print(g,s)
except : pass


T = int(input())

def get_gcd(x, y):
 while(y):
  x, y = y, x % y
 return x

for _ in range(T):
 N = int(input())
 num = list(map(int, input().split()))
 gcd = num[0]
 for n in num[1:]:
  gcd = get_gcd(gcd, n)
 print(gcd, sum(num)//gcd)


def find_gcd(x, y): 
 while(y): 
  x, y = y, x % y 
 return x

t = int(input())
for i in range(t):
 n = int(input())
 if(n == 1):
  cost = 1
  gcd = int(input())
 else :
  number = list(map(int,input().split()))
  num1 = number[0] 
  num2 = number[1] 
  gcd = find_gcd(num1, num2) 
  for i in range(2, len(number)): 
   gcd = find_gcd(gcd, number[i]) 
  cost = sum(number)//gcd
 print(str(gcd)+ " "+ str(cost))

from math import gcd, ceil
t = int(input())
for _ in range(t):
 n = int(input())
 arr = list(map(int, input().split()))
 gcdd = arr[0]
 for i in range(1, n):
  gcdd = gcd(arr[i], gcdd)
 print(gcdd, int(ceil(sum(arr) / gcdd))) 

from fractions import gcd
from functools import reduce

t=int(input())
for i in range(0,t):
 n=int(input())
 a=list(map(int,input().split()))
 r1= reduce(gcd, a)
 r2= sum(a)//r1
 print(r1,r2)


# cook your dish here
try:
 def find_gcd(x, y): 
  
  while(y): 
   x, y = y, x % y 
   
  return x 
 for _ in range(int(input())):
  n=int(input())
  l=list(map(int,input().split()))
  if n==1:
   print(l[0],1)
   continue
  g=find_gcd(l[0],l[1])
  for i in range(2,n):
   g=find_gcd(g,l[i])
  s=0
  for i in l:
   s+=i/g
  print(g,int(s))
except:pass 

from math import gcd, ceil
t = int(input())
for _ in range(t):
 n = int(input())
 arr = list(map(int, input().split()))
 gcdd = arr[0]
 for i in range(1, n):
  gcdd = gcd(arr[i], gcdd)
 print(gcdd, int(ceil(sum(arr) / gcdd))) 

from fractions import gcd
from functools import reduce
t=int(input())
for _ in range(t):
 n = int(input())
 list1 = list(map(int, input().split()))
 r= reduce(gcd, list1)
 r1= sum(list1)//r
 print(r,r1)

# cook your dish here
def gcd(x, y):
 while y:
  x, y = y, x % y
 return x

def lcm(x, y):
 return (x*y)//(gcd(x,y))

def isPrime(n) : 
 if (n <= 1) : 
  return False
 if (n <= 3) : 
  return True
 if (n % 2 == 0 or n % 3 == 0) : 
  return False
 i = 5
 while(i * i <= n) : 
  if (n % i == 0 or n % (i + 2) == 0) : 
   return False
  i = i + 6
 return True

abc="abcdefghijklmnopqrstuvwxyz"

pi=3.141592653589793238


def find_common(a):
 gcd_ = a[0]
 for i in range(1,len(a)):
  gcd_ = gcd(gcd_,a[i])
 return(gcd_)


t = int(input())
for _ in range(t):
 n = int(input())
 arr = list(map(int,input().split()))
 total = sum(arr)
 
 unit_size = find_common(arr)
 units = 0
 for i in arr:
  units = units + i//unit_size
 print(unit_size,units)
 
 
 
 
 
 
 
 
 
 


import math

test = int(input())
for _ in range(test):
 n = int(input())
 arr = [int(i) for i in input().split()]
 if len(arr) < 2:
  print(str(arr[0])+" "+str(1))
  continue
 num1 = arr[0] 
 num2 = arr[1] 
 gcd = math.gcd(num1,num2)
 for i in range(2, len(arr)): 
  gcd = math.gcd(gcd, arr[i]) 
 cost = 0
 for i in range(len(arr)):
  cost += (arr[i]/gcd)
 print(str(gcd)+" "+str(int(cost)))

# cook your dish here
from fractions import gcd
from functools import reduce

t=int(input())
for i in range(0,t):
 n=int(input())
 arr=list(map(int,input().split()))
 res= reduce(gcd, arr)
 res1= sum(arr)//res 
 print(res,res1)


import math
for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 gc=a[0]
 for i in a :
  gc=math.gcd(gc,i)
 print(gc,sum(a)//gc)

# cook your dish here
import math
def find_gcd(x, y): 
 while(y): 
  x, y = y, x % y 
 
 return x 
t=int(input())
for i in range(0,t):
 n=int(input())
 l=list(map(int,input().split()))
 l.sort()
 x=len(l)
 if(x>2):
  num1=l[0] 
  num2=l[1] 
  gcd=find_gcd(num1,num2) 
  for i in range(2,len(l)): 
   gcd=find_gcd(gcd,l[i]) 
 elif(x==2):
  gcd=math.gcd(l[0],l[1])
 else:
  gcd=l[0]
 c=sum(l)//gcd
 print(gcd,c)





def main():
 t = int(input())
 for i in range(t):
  N = int(input())
  l = list(map(int, input().split()))
  c=0
  gcd=0
  for j in range(min(l), 0 ,-1):
   c=0
   for k in l:
    if k%j !=0:
     break
    else:
     c+=1
   if c == len(l):
    gcd = j
    break
  cost=0
  for j in l:
   cost+= j // gcd
  print(gcd, cost)
def __starting_point():
 main()
# cook your dish here
# cook your dish here

__starting_point()

# cook your dish here
import math
t = int(input())
for i in range(t):
 n = int(input())
 lst = list(map(int, input().split()))
 lst = sorted(lst)
 minimum = min(lst)
 x = 1
 xlist=[]
 for k in range(1, minimum+1):
  for j in lst:
   if j%k==0:
    xlist.append(k)
   else:
    break
 xlist = sorted(xlist, reverse = True)
 for m in xlist:
  if xlist.count(m)==n:
   print(m,math.ceil(sum(lst)/m))
   break
    
  
  
  






def main():
 t = int(input())
 for i in range(t):
  N = int(input())
  l = list(map(int, input().split()))
  c=0
  gcd=0
  for j in range(min(l), 0 ,-1):
   c=0
   for k in l:
    if k%j !=0:
     break
    else:
     c+=1
   if c == len(l):
    gcd = j
    break
  cost=0
  for j in l:
   cost+= j // gcd
  print(gcd, cost)
def __starting_point():
 main()
# cook your dish here
# cook your dish here

__starting_point()

# cook your dish here
import math
t=int(input())
while t>0:
 n=int(input())
 arr=list(map(int,input().split()))
 y=0
 for x in arr:
  y=math.gcd(x,y)
  if y==1:
   break
 z=sum(arr)
 print(y,' ',z//y)
 t-=1

# cook your dish here
def factors(n):
 res=[]
 for i in range (n//2,0,-1):
  if (n%i==0):
   res.append(i)
 return res

def wires(w):
 w.sort()
 a=w[0]
 cost=0
 for num in w:
  if (num%a!=0):
   fact=factors(a)
   break
  cost=cost+(num//a)
 else:
  print(a,cost)
  return None
 for char in fact:
  cost=0
  for num in w:
   if (num%char!=0):
    break
   cost=cost+(num//char)
  else:
   print(char,cost)
   return None
 
t=int(input())
for _ in range (t):
 n=int(input())
 w=[int(x) for x in input().split()]
 wires(w)

import math
for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 gc=a[0]
 for i in a :
  gc=math.gcd(gc,i)
 print(gc,sum(a)//gc)



# cook your dish here
def find_gcd(x, y): 
 while(y): 
  x, y = y, x % y 
 
 return x 
n=int(input())
for i in range(n):
 n1=int(input())
 l=list(map(int,input().split()))
 if(n1==1):
  print(l[0],1)
 else:    
  num1=l[0] 
  num2=l[1] 
  gcd=find_gcd(num1,num2) 
  for i in range(2,len(l)): 
   gcd=find_gcd(gcd,l[i]) 
  sum1=0 
  for i in range(n1):
   sum1+=(l[i]//gcd)
  print(gcd,int(sum1)) 


import re
import math as mt
def __starting_point():
 T=int(input())
 while T:
  n=int(input())
  lt=[int(x) for x in input().split()]
  p=0
  sm=sum(lt)
  for x in range(n):
   p=mt.gcd(p,lt[x])
   
 
  print(p,sm//p)
  T=T-1
__starting_point()

# cook your dish here
def gcd(a, b):
 if(b==0): 
  return a 
 else: 
  return gcd(b,a%b) 
  
  
t = int(input())
for _ in range(t):
 n = int(input())
 a = list(map(int, input().split()))
 res = a[0]
 for i in a[1:]:
  res = gcd(res, i)
 tot = 0
 for i in a:
  tot += i//res
 print(res, tot)