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: UNKNOWN_DIFFICULTY

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)


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)


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)


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 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)


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.141592653589793

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)))


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)


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()
__starting_point()


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


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


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()


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)