WLD likes playing with codes.One day he is writing a function.Howerver,his computer breaks down because the function is too powerful.He is very sad.Can you help him?
The function:
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;
}
输入解释
There are Multiple Cases.(At MOST $10$)
For each case:
The first line contains an integer $N(1 \leq N \leq 10000)$.
The next line contains $N$ integers $a1,a2,...,aN(1 \leq ai \leq 10000)$.
输出解释
For each case:
Print an integer,denoting what the function returns.
输入样例
5
1 3 4 2 4
输出样例
64
提示
gcd(x,y) means the greatest common divisor of x and y.