#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,x,n) rep(I,0,n){cout<<(I ? " ":"")<<A[I]x;}cout<<endl;
#define pprint(A,y,m,n) rep(J,0,m){print(A[J],y,n);}
const long mod=1e9+7;
const int siz=2e5+1;
const long inf=1e9;
int main(){
	int N; cin>>N;
	string s; long y;
	int cnt[60][60] = {};
	long ans = 0;
	rep(_,0,N){
		cin>>s; y = 0;
        int k = 0;
        rep(i,0,s.size()){
            if(s[i] == '.') k = s.size() - i - 1;
            else (y *= 10) += s[i] - '0';
        }
        int a = -k,b = -k;
        while(y % 2 == 0){ y /= 2; a++; }
        while(y % 5 == 0){ y /= 5; b++; }
        ans += cnt[-a+30][-b+30];
        rep(i,-30,a+1)rep(j,-30,b+1) cnt[i+30][j+30]++;
	}cout<<ans<<endl;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

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 rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,x,n) rep(I,0,n){cout<<(I ? " ":"")<<A[I]x;}cout<<endl;
#define pprint(A,y,m,n) rep(J,0,m){print(A[J],y,n);}
const long mod=1e9+7;
const int siz=2e5+1;
const long inf=1e9;
int main(){
	int N; cin>>N;
	string s; long y;
	int cnt[60][60] = {};
	long ans = 0;
	rep(_,0,N){
		cin>>s; y = 0;
        int k = 0;
        rep(i,0,s.size()){
            if(s[i] == '.') k = s.size() - i - 1;
            else (y *= 10) += s[i] - '0';
        }
        int a = -k,b = -k;
        while(y % 2 == 0){ y /= 2; a++; }
        while(y % 5 == 0){ y /= 5; b++; }
        ans += cnt[-a+30][-b+30];
        rep(i,-30,a+1)rep(j,-30,b+1) cnt[i+30][j+30]++;
	}cout<<ans<<endl;
}

```