Code

wld有一个长度为n的序列a1..an
wld想要你给出下面这段c++代码的输出：
int calc()
{
	int res=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			res+=gcd(a[i],a[j])*(gcd(a[i],a[j])-1);
			res%=10007;
		}
	return res;
}
保证$1 \leq n \leq 10000, 1 \leq ai \leq 10000$ (对于任意$1 \leq i \leq n$)

多组数据(最多$10$组)
对于每组数据：
第一行：一个数n表示序列的长度
第二行：$n$个数，依次为$a1, a2, … ,an$

对于每组数据：
输出calc函数的返回值

5
1 3 4 2 4

64

gcd(i,j)为两数的最大公因数。