Let there be a K-dimensional Hyperrectangle, where each dimension has a length of n_{1},n_{2},...n_{k}. 

Each of the Hyperrectangle's unit cells is addressed at (i,j,k,...) and has a value which is equivalent to GCD(i,j,k,...) where 1 <= i <= n_{1} , 1 <= j <= n_{2} ....  

The goal is to sum all the GCD(i,j,k,...) cell values and print the result modulo 10^9 + 7. Note that indexing is from 1 to N and not 0 to N-1. 

Input Format 

The first line contains an integer T. T testcases follow. 

Each testcase contains 2 lines, the first line being K (K-dimension) and the second line contains K space separated integers indicating the size of each dimension - 
n_{1} n_{2} n_{3} ... n_{k}

Output Format 

Print the sum of all the hyperrectangle cell's GCD values modulo 10^9 + 7 in each line corresponding to each test case. 

Constraints 

1 <= T <= 1000 

2 <= K <= 500 

1 <= n_{k} <= 100000

Sample Input #00  

2
2
4 4
2
3 3

Sample Output #00 

24
12

Sample Input #01  

1
3
3 3 3

Sample Output #01

30

Explanation #00 

For the first test case, it's a 4X4 2-dimension Rectangle. The (i,j) address and GCD values of each element at (i,j) will look like  

1,1 1,2 1,3 1,4              1 1 1 1  
2,1 2,2 2,3 2,4  => GCD(i,j) 1 2 1 2  
3,1 3,2 3,3 3,4              1 1 3 1  
4,1 4,2 4,3 4,4              1 2 1 4  

Sum of these values is 24  

Explanation #00 

Similarly for 3X3 GCD (i,j) would look like 

1,1 1,2 1,3               1 1 1  
2,1 2,2 2,3  => GCD(i,j)  1 2 1  
3,1 3,2 3,3               1 1 3  

Sum is 12 

Explanation #01 

Here we have a 3-dimensional 3X3X3 Hyperrectangle or a cube. We can write it's GCD (i,j,k) values in 3 layers. 

1,1,1 1,1,2 1,1,3  |  2,1,1 2,1,2 2,1,3  |  3,1,1 3,1,2 3,1,3  
1,2,1 1,2,2 1,2,3  |  2,2,1 2,2,2 2,2,3  |  3,2,1 3,2,2 3,2,3  
1,3,1 1,3,2 1,3,3  |  2,3,1 2,3,2 2,3,3  |  3,3,1 3,3,2 3,3,3  
GCD (i,j,k)
1 1 1              |  1 1 1              |  1 1 1  
1 1 1              |  1 2 1              |  1 1 1  
1 1 1              |  1 1 1              |  1 1 3  

Total Sum = 30

Timelimits
Timelimits for this challenge is given here

Source: hackerrank | Difficulty: MEDIUM
Tags: Number theory


Solutions:
g = [-1] * 100000
g[1] = 1
for n in range(2, 100000):
	g[n] += n
	rn = 2 * n
	while rn < 100000:
		g[rn] -= g[n]
		rn += n

def solve(A):
	result = 0
	i = 1
	while True:
		Ap = tuple((a // i for a in A))
		if any((a == 0 for a in Ap)):
			return result
		p = g[i]
		for a in Ap:
			p *= a
			p %= 1000000007
		result += p
		result %= 1000000007
		i += 1
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
	K = int(stdin.readline())
	A = tuple(map(int, stdin.readline().split()))
	print(solve(A))


M = 100010
P = 1000000007
delta = [0] * M
for i in range(1, M):
	delta[i] += i
	for j in range(i + i, M, i):
		delta[j] -= delta[i]
t = int(input())
for ca in range(t):
	k = int(input())
	nList = [int(tok) for tok in input().split()]
	m = max(nList)
	res = 0
	for i in range(1, m + 1):
		prod = 1
		for n in nList:
			prod *= n // i
		if prod == 0:
			break
		res = (res + prod * delta[i]) % P
	print((res + P) % P)


import functools
import operator
MODULO = 10 ** 9 + 7
MAX_N = 100000

def totient(n):
	totient = list(range(n))
	for i in range(1, n):
		for multiply_i in range(i * 2, n, i):
			totient[multiply_i] -= totient[i]
	return totient

def product(iterable, start=1):
	return functools.reduce(operator.mul, iterable, start)

def sum_gcd(nk, totients):
	sum = 0
	for gcd in range(1, min(nk) + 1):
		sum += totients[gcd] * product((n // gcd for n in nk))
	return sum

def main():
	totients = totient(MAX_N + 1)
	T = int(input())
	for t in range(T):
		K = int(input())
		nk = [int(n) for n in input().split()]
		print(sum_gcd(nk, totients) % MODULO)
main()


import functools
import operator
MODULO = 10 ** 9 + 7
MAX_N = 100000

def totient(n):
	totient = list(range(n))
	for i in range(1, n):
		for multiply_i in range(i * 2, n, i):
			totient[multiply_i] -= totient[i]
	return totient

def product(iterable, start=1):
	return functools.reduce(operator.mul, iterable, start)

def sum_gcd(nk, totients):
	sum = 0
	for gcd in range(1, min(nk) + 1):
		sum += totients[gcd] * product((n // gcd for n in nk))
	return sum

def main():
	totients = totient(MAX_N + 1)
	T = int(input())
	for t in range(T):
		K = int(input())
		nk = [int(n) for n in input().split()]
		print(sum_gcd(nk, totients) % MODULO)
main()


from functools import reduce
(N, M) = (10 ** 5, 10 ** 9 + 7)
for _ in range(int(input())):
	(n, data) = (input(), list(map(int, input().rstrip().split(' '))))
	(k, r) = (min(data), 0)
	h = [reduce(lambda s, t: t // (1 if i == 0 else i) * s % M, data, 1) for i in range(0, k + 1)]
	for i in range(k, 1, -1):
		(mp, q) = (k // i, 0)
		for p in range(2, k + 1):
			if p > mp:
				break
			h[i] -= h[p * i]
		r = (r + h[i] * i) % M
	print(((r + h[1] - sum(h[2:])) % M + M) % M)


mod = 1000000007

def phi(d):
	ans = 1
	for (prime, exp) in d.items():
		ans = ans * (prime - 1) * pow(prime, exp - 1)
	return ans

def sieve(bound):
	arr = [1 for i in range(bound - 2)]
	arr.insert(0, 0)
	arr.insert(0, 0)
	ps = []
	l = len(arr)
	sq = 0
	for (i, val) in enumerate(arr):
		if sq > bound:
			break
		elif val == 1:
			ind = i
			ps.append(i)
			for ind in range(sq, l, i):
				arr[ind] = 0
		sq = sq + 2 * i + 1
	for j in range(i, l):
		if arr[j] == 1:
			ps.append(j)
	return ps

def sieve_factor(n, primes):
	d = dict()
	for div in primes:
		while n % div == 0:
			if div in d:
				d[div] += 1
			else:
				d[div] = 1
			n = n // div
		if n == 1:
			break
		if div * div > n:
			d[n] = 1
			break
	if n != 1:
		d[n] = 1
	return d

def all_phi(n):
	l = [0, 1]
	primes = sieve(n)
	prime_set = set(primes)
	for i in range(2, n + 1):
		if i in prime_set:
			l.append(i - 1)
		else:
			d = sieve_factor(i, primes)
			l.append(phi(d))
	return l

def solve(n):
	small = min(n)
	phis = all_phi(small)
	total = 0
	prod = 1
	for i in range(len(n)):
		prod = prod * n[i] % mod
	total += prod
	for i in range(2, small + 1):
		prod = 1
		for j in range(len(n)):
			prod = prod * (n[j] // i) % mod
		prod = prod * phis[i]
		total = (total + prod) % mod
	return total
t = int(input())
for _ in range(t):
	n_count = int(input())
	n = list(map(int, input().rstrip().split()))
	print(solve(n))


def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None
from math import ceil

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


import math
import os
import random
import re
import sys
from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


g = [-1] * 100000
g[1] = 1
for n in range(2, 100000):
	g[n] += n
	rn = 2 * n
	while rn < 100000:
		g[rn] -= g[n]
		rn += n

def solve(A):
	result = 0
	i = 1
	while True:
		Ap = tuple((a // i for a in A))
		if any((a == 0 for a in Ap)):
			return result
		p = g[i]
		for a in Ap:
			p *= a
			p %= 1000000007
		result += p
		result %= 1000000007
		i += 1
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
	K = int(stdin.readline())
	A = tuple(map(int, stdin.readline().split()))
	print(solve(A))


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


g = [-1] * 100000
g[1] = 1
for n in range(2, 100000):
	g[n] += n
	rn = 2 * n
	while rn < 100000:
		g[rn] -= g[n]
		rn += n

def solve(A):
	result = 0
	i = 1
	while True:
		Ap = tuple((a // i for a in A))
		if any((a == 0 for a in Ap)):
			return result
		p = g[i]
		for a in Ap:
			p *= a
			p %= 1000000007
		result += p
		result %= 1000000007
		i += 1
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
	K = int(stdin.readline())
	A = tuple(map(int, stdin.readline().split()))
	print(solve(A))


g = [-1] * 100000
g[1] = 1
for n in range(2, 100000):
	g[n] += n
	rn = 2 * n
	while rn < 100000:
		g[rn] -= g[n]
		rn += n

def solve(A):
	result = 0
	i = 1
	while True:
		Ap = tuple((a // i for a in A))
		if any((a == 0 for a in Ap)):
			return result
		p = g[i]
		for a in Ap:
			p *= a
			p %= 1000000007
		result += p
		result %= 1000000007
		i += 1
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
	K = int(stdin.readline())
	A = tuple(map(int, stdin.readline().split()))
	print(solve(A))


g = [-1] * 100000
g[1] = 1
for n in range(2, 100000):
	g[n] += n
	rn = 2 * n
	while rn < 100000:
		g[rn] -= g[n]
		rn += n

def solve(A):
	result = 0
	i = 1
	while True:
		Ap = tuple((a // i for a in A))
		if any((a == 0 for a in Ap)):
			return result
		p = g[i]
		for a in Ap:
			p *= a
			p %= 1000000007
		result += p
		result %= 1000000007
		i += 1
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
	K = int(stdin.readline())
	A = tuple(map(int, stdin.readline().split()))
	print(solve(A))


g = [-1] * 100000
g[1] = 1
for n in range(2, 100000):
	g[n] += n
	rn = 2 * n
	while rn < 100000:
		g[rn] -= g[n]
		rn += n

def solve(A):
	result = 0
	i = 1
	while True:
		Ap = tuple((a // i for a in A))
		if any((a == 0 for a in Ap)):
			return result
		p = g[i]
		for a in Ap:
			p *= a
			p %= 1000000007
		result += p
		result %= 1000000007
		i += 1
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
	K = int(stdin.readline())
	A = tuple(map(int, stdin.readline().split()))
	print(solve(A))


import math
import os
import random
import re
import sys
from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


import math
import os
import random
import re
import sys
from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


import math
import os
import random
import re
import sys
from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


import math
import os
import random
import re
import sys
from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)


import math
import os
import random
import re
import sys
from math import ceil

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	while a != 0:
		(a, b) = (b % a, a)
	return b

def product(lst):
	prod = 1
	for n in lst:
		prod = prod * n % (10 ** 9 + 7)
	return prod
bounds = None
cache = None

def coprime_count(divisor):
	if divisor > bounds[-1] // 2:
		return 1
	if divisor in cache:
		return cache[divisor]
	scaled_bounds = [n // divisor for n in bounds]
	total = product(scaled_bounds)
	cap = scaled_bounds[0]
	rest = sum((coprime_count(divisor * d) for d in range(2, cap + 1)))
	cache[divisor] = (total - rest) % (10 ** 9 + 7)
	return cache[divisor]
t = int(input())
for _ in range(t):
	k = int(input())
	bounds = list(map(int, input().split()))
	bounds.sort()
	cache = dict()
	total = 0
	for i in range(1, bounds[0] + 1):
		total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
	print(total)