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.