#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
typedef long long ll;
typedef long double ld;
using namespace std;

int sum[19][19]={};

int main() {
	int N;
	cin >> N;
	ll ans=0;
	for(int i=0; i<N; ++i){
	    string S;
	    cin >> S;
	    bool flag=false;
	    ll s=0LL;
	    int u=9;
	    for(int j=0; j<S.size(); ++j){
	        if(flag) --u;
	        if(S[j]=='.') flag=true;
	        else (s *= 10) += S[j]-'0';
	    }
	    while(u){
	        s *= 10;
	        --u;
	    }
	    int t=0, f=0;
	    while(s%2==0 && t<18){
	        ++t;
	        s /= 2;
	    }
	    while(s%5==0 && f<18){
	        ++f;
	        s /= 5;
	    }
	    ans += sum[18-t][18-f];
	    for(int j=0; j<=t; ++j){
	        for(int k=0; k<=f; ++k){
	            ++sum[j][k];
	        }
	    }
	}
	cout << ans << endl;
	return 0;
}

### Prompt

Create a solution in CPP for 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 <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
typedef long long ll;
typedef long double ld;
using namespace std;

int sum[19][19]={};

int main() {
	int N;
	cin >> N;
	ll ans=0;
	for(int i=0; i<N; ++i){
	    string S;
	    cin >> S;
	    bool flag=false;
	    ll s=0LL;
	    int u=9;
	    for(int j=0; j<S.size(); ++j){
	        if(flag) --u;
	        if(S[j]=='.') flag=true;
	        else (s *= 10) += S[j]-'0';
	    }
	    while(u){
	        s *= 10;
	        --u;
	    }
	    int t=0, f=0;
	    while(s%2==0 && t<18){
	        ++t;
	        s /= 2;
	    }
	    while(s%5==0 && f<18){
	        ++f;
	        s /= 5;
	    }
	    ans += sum[18-t][18-f];
	    for(int j=0; j<=t; ++j){
	        for(int k=0; k<=f; ++k){
	            ++sum[j][k];
	        }
	    }
	}
	cout << ans << endl;
	return 0;
}

```