#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
const int M=25;
long double a[N];
int num[N];
int tf[M][M]={0};
int num_2,num_5,ans=0,n;
void get(int y)
{
	int x=y;
    num_2=num_5=0;
    while (x%2==0)
    {
        num_2++;
        x=x/2;
    }
    x=y;
    while (x%5==0)
    {
        num_5++;
        x=x/5;
    }
}
signed main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    long double t=1e9;
    for (int i=1;i<=n;i++) a[i]=a[i]*t;
    for (int i=1;i<=n;i++) num[i]=a[i]+0.99;
    for (int i=1;i<=n;i++)
    {
        get(num[i]);
        num_2=min(18LL,num_2),num_5=min(18LL,num_5);
        //有ttwo个2，ffive个5
        for (int i=18-num_2;i<=18;i++)
            for (int j=18-num_5;j<=18;j++) ans+=tf[i][j];
        tf[num_2][num_5]++;
    }
    cout<<ans<<endl;
}
### Prompt

Develop a solution in Cpp to the problem described below:

You are given N real values A_1, A_2, \ldots, A_N. Compute the number of pairs of indices (i, j) such that i < j and the product A_i \cdot A_j is integer.

Constraints

* 2 \leq N \leq 200\,000
* 0 < A_i < 10^4
* A_i is given with at most 9 digits after the decimal.

Input

Input is given from Standard Input in the following format.


N
A_1
A_2
\vdots
A_N


Output

Print the number of pairs with integer product A_i \cdot A_j (and i < j).

Examples

Input

5
7.5
2.4
17.000000001
17
16.000000000


Output

3


Input

11
0.9
1
1
1.25
2.30000
5
70
0.000000001
9999.999999999
0.999999999
1.000000001


Output

8

### Response

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
const int M=25;
long double a[N];
int num[N];
int tf[M][M]={0};
int num_2,num_5,ans=0,n;
void get(int y)
{
	int x=y;
    num_2=num_5=0;
    while (x%2==0)
    {
        num_2++;
        x=x/2;
    }
    x=y;
    while (x%5==0)
    {
        num_5++;
        x=x/5;
    }
}
signed main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    long double t=1e9;
    for (int i=1;i<=n;i++) a[i]=a[i]*t;
    for (int i=1;i<=n;i++) num[i]=a[i]+0.99;
    for (int i=1;i<=n;i++)
    {
        get(num[i]);
        num_2=min(18LL,num_2),num_5=min(18LL,num_5);
        //有ttwo个2，ffive个5
        for (int i=18-num_2;i<=18;i++)
            for (int j=18-num_5;j<=18;j++) ans+=tf[i][j];
        tf[num_2][num_5]++;
    }
    cout<<ans<<endl;
}
```