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;
}
Input
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)$.
Output
For each case:
Print an integer,denoting what the function returns.
Sample Input
5
1 3 4 2 4
Sample Output
64
Hint
gcd(x,y) means the greatest common divisor of x and y.
