#include<bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
    int inf=1000000000,x,i1,i2,j1,j2,ans=0,n,i;
     long double d;
     int a[47][21];
     cin>>n;
     memset(a,0,sizeof(a));
     for(i=1;i<=n;i++){
         cin>>d;
         i1=0,i2=0;
         x=(int)(round(d*1e9));
         while(x%2==0){x/=2;i1++;}
         while(x%5==0){x/=5,i2++;}
         a[i1][i2]++;
     }
     for(i1=0;i1<=45;i1++){
         for(j1=0;j1<=20;j1++){
             for(i2=0;i2<=45;i2++){
                 for(j2=0;j2<=20;j2++){
                     if(i2<i1||(i2==i1&&j1>j2))continue;
                     if(min(i1+i2,j1+j2)>=18){if(i1==i2&&j1==j2){x=a[i1][j1];
                         ans+=(x*(x-1))/2;continue;
                     }
                         ans+=a[i1][j1]*a[i2][j2];}
                 }
             }
         }
     }
     cout<<ans;
    return 0;
}
### 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>
using namespace std;
#define int long long int
int32_t main(){
    int inf=1000000000,x,i1,i2,j1,j2,ans=0,n,i;
     long double d;
     int a[47][21];
     cin>>n;
     memset(a,0,sizeof(a));
     for(i=1;i<=n;i++){
         cin>>d;
         i1=0,i2=0;
         x=(int)(round(d*1e9));
         while(x%2==0){x/=2;i1++;}
         while(x%5==0){x/=5,i2++;}
         a[i1][i2]++;
     }
     for(i1=0;i1<=45;i1++){
         for(j1=0;j1<=20;j1++){
             for(i2=0;i2<=45;i2++){
                 for(j2=0;j2<=20;j2++){
                     if(i2<i1||(i2==i1&&j1>j2))continue;
                     if(min(i1+i2,j1+j2)>=18){if(i1==i2&&j1==j2){x=a[i1][j1];
                         ans+=(x*(x-1))/2;continue;
                     }
                         ans+=a[i1][j1]*a[i2][j2];}
                 }
             }
         }
     }
     cout<<ans;
    return 0;
}
```