#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
int x[200010],y[200010],f[19][19];
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	rep(i,19)rep(j,19)f[i][j]=0;
	int n;
	cin>>n;
	ll ans=0;
	rep(i,n){
		string s;
		cin>>s;
		bool th=0;
		rep(j,s.size())th|=(s[j]=='.');
		if(!th)s+='.';
		ll A=0;
		rep(j,s.size()){
			if(s[j]=='.'){
				while(s.size()<j+10)s+='0';
			}
			else{
				A*=10;
				A+=s[j]-'0';
			}
		}
		x[i]=0;
		while(A%2==0){
			A/=2;
			x[i]++;
		}
		y[i]=0;
		while(A%5==0){
			A/=5;
			y[i]++;
		}
		chmin(x[i],18);
		chmin(y[i],18);
		for(int p=18-x[i];p<19;p++){
			for(int q=18-y[i];q<19;q++){
				ans+=f[p][q];
			}
		}
		f[x[i]][y[i]]++;
	}
	cout<<ans<<endl;
}

### Prompt

Please formulate 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<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
int x[200010],y[200010],f[19][19];
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	rep(i,19)rep(j,19)f[i][j]=0;
	int n;
	cin>>n;
	ll ans=0;
	rep(i,n){
		string s;
		cin>>s;
		bool th=0;
		rep(j,s.size())th|=(s[j]=='.');
		if(!th)s+='.';
		ll A=0;
		rep(j,s.size()){
			if(s[j]=='.'){
				while(s.size()<j+10)s+='0';
			}
			else{
				A*=10;
				A+=s[j]-'0';
			}
		}
		x[i]=0;
		while(A%2==0){
			A/=2;
			x[i]++;
		}
		y[i]=0;
		while(A%5==0){
			A/=5;
			y[i]++;
		}
		chmin(x[i],18);
		chmin(y[i],18);
		for(int p=18-x[i];p<19;p++){
			for(int q=18-y[i];q<19;q++){
				ans+=f[p][q];
			}
		}
		f[x[i]][y[i]]++;
	}
	cout<<ans<<endl;
}

```