You are given an array A of size N.

In one operation, you can do the following:

Choose any two adjacent elements A_{i} and A_{i+1} (1 ≤ i < N).
Let X = gcd(A_{i},A_{i+1}) and Y = lcm(A_{i},A_{i+1}). Here gcd denotes the [greatest common divisor] and lcm denotes the [least common multiple] respectively.
Replace A_{i} with X and A_{i+1} with Y.

Find the maximum value of \Sigma^{N}_{i=1}A_{i} you can achieve, after performing the above operation any (possibly zero) number of times.  
Since the result may be very large, you need to output the result modulo 10^{9}+7.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the size of A.
- The next line contains N space-separated integers A_{1},A_{2},\ldots,A_{N}, the elements of the array.

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

For each test case, output the maximum value of \Sigma^{N}_{i=1}A_{i} you can achieve, after performing the above operation any (possibly zero) number of times, modulo 10^{9}+7.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$
- The sum of $N$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
3
4
4 4 6 1
3
108 24 18
10
93179 93187 93199 93229 93239 93241 93251 93253 93257 93263

----- Sample Output 1 ------ 
19
258
392286903

----- explanation 1 ------ 
Test case $1$: Initially, $A=[4,4,6,1]$.
- Operation $1$: Choose $A_{2},A_{3}$. Thus, $X = gcd(4, 6) = 2$ and $Y = lcm(4, 6) = 12$. Thus $A$ becomes $[4,2,12,1]$.

The sum of the array is $4+2+12+1 = 19$. It can be shown that this is the maximum sum of array we can achieve after applying any number of operations.

Test case $2$: Initially, $A=[108,24,18]$.
- Operation $1$: Choose $A_{1},A_{2}$. Thus, $X = gcd(108, 24) = 12$ and $Y = lcm(108, 24) = 216$. Thus $A$ becomes $[12, 216, 18]$.
- Operation $2$: Choose $A_{2},A_{3}$. Thus, $X = gcd(216, 18) = 18$ and $Y = lcm(216, 18) = 216$. Thus $A$ becomes $[12, 18, 216]$.
- Operation $3$: Choose $A_{1},A_{2}$. Thus, $X = gcd(12, 18) = 6$ and $Y = lcm(12, 18) = 36$. Thus $A$ becomes $[6, 36, 216]$.

The sum of the array is $6+36+216 = 258$. It can be shown that this is the maximum sum of array we can achieve after applying any number of operations.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Sorting

Mathematics


Solutions:
import itertools
m = 10 ** 9 + 7

def factorize(n):

	def try_divisor(n, k, pfs):
		if n % k == 0:
			pfs[k] = 1
			n //= k
			while n % k == 0:
				pfs[k] += 1
				n //= k
		return n
	pfs = {}
	n = try_divisor(n, 2, pfs)
	n = try_divisor(n, 3, pfs)
	for i in itertools.count(start=1):
		n = try_divisor(n, 6 * i - 1, pfs)
		n = try_divisor(n, 6 * i + 1, pfs)
		if (6 * i + 1) ** 2 > n:
			break
	if n > 1:
		pfs[n] = 1
	return pfs
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	assert len(a) == n
	p_lists = {}
	for x in a:
		for (p, e) in factorize(x).items():
			if p not in p_lists:
				p_lists[p] = []
			p_lists[p].append(p ** e)
	for v in p_lists.values():
		v.sort()
	sum = 0
	for __ in range(n):
		prod = 1
		for p in list(p_lists):
			ppow = p_lists[p].pop()
			if len(p_lists[p]) == 0:
				del p_lists[p]
			prod = prod * ppow % m
		sum = (sum + prod) % m
	print(sum)


from math import sqrt
from sys import stdin
input = stdin.readline
MODULO = 10 ** 9 + 7
MAX = 10 ** 6

def eratosthenes(n):
	numbers = [True] * (n + 1)
	(p, p2) = (2, 4)
	while p2 <= n:
		if numbers[p]:
			for i in range(p2, n + 1, p):
				numbers[i] = False
		p += 1
		p2 = p * p
	return [2] + [number for number in range(3, n + 1, 2) if numbers[number]]

def factorization(n, primeslist=None):
	pf = []
	if primeslist == None:
		primeslist = eratosthenes(int(sqrt(n)) + 1)
	for p in primeslist:
		if p * p > n:
			break
		count = 0
		while n % p == 0:
			n //= p
			count += 1
		if count > 0:
			pf.append((p, count))
	if n > 1:
		pf.append((n, 1))
	return pf

def solve(N, A, primeslist):
	P = len(primeslist)
	prime = {p: [] for p in primeslist}
	for a in A:
		for (p, c) in factorization(a, primeslist):
			prime[p].append(c)
	A = [1] * N
	for p in prime:
		for (i, c) in enumerate(sorted(prime[p], reverse=True)):
			A[i] *= p ** c
	return sum(A) % MODULO
T = int(input().strip())
primeslist = eratosthenes(MAX)
for problem in range(1, T + 1):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()]
	print(solve(N, A, primeslist))