Monk is very busy with a problem and he has to leave for the celebration of Holika Dahan. He asks you to help him with the problem so that he can enjoy with his friends.
Let us define the division function F(n) as:
If Decimal part of n is >=0.5 we take ceil of n else we take floor of n.
Eg. F(4.51)=5, F(4.49)=4.
Given an array A of size N . Compute the all pair division function.
ans=0;
For(i=0;i<N;i++)
{
For(j=0;j<N;j++)
{
ans=ans+F(A[i]/A[j])
}
}
return ans;
Input Format
First line contains an integer T denoting the number of test cases.
Each test case contains two lines:
First line contains an integer N.
Next line contains N space separated integers denoting array A.
Output Format:
For each test case, print the value returned from all pair division function.
Input Constraints:
1≤T≤10
1≤N≤105
1≤A[i]≤105
F(1/1)=1 F(1/2)=1 F(1/3)=0
F(2/1)=2 F(2/2)=1 F(2/3)=1
F(3/1)=3 F(3/2)=2 F(3/3)=1
The sum is 12.