#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long double ld;
const int N=200005;
int n,v1[N],v2[N],val[100][100];
long double a[N];
long long ans,num[N];
int calc2(long long x){
	int res=0;
	while(x%2==0){
		res++;
		x/=2;
	}
	return res;
}
int calc5(long long x){
	int res=0;
	while(x%5==0){
		res++;
		x/=5;
	}
	return res;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%Lf",&a[i]);
		num[i]=a[i]*1e9+0.5;
		v1[i]=calc2(num[i])-9;
		v2[i]=calc5(num[i])-9;
	}
	for(int i=n;i>=1;i--){
		for(int j=-v1[i];j<=32;j++){
			for(int k=-v2[i];k<=15;k++){
				ans+=val[j+32][k+15];
			}
		}
		val[v1[i]+32][v2[i]+15]++;
	}
	printf("%lld\n",ans);
	return 0;
}
### Prompt

Please create a solution in cpp 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<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long double ld;
const int N=200005;
int n,v1[N],v2[N],val[100][100];
long double a[N];
long long ans,num[N];
int calc2(long long x){
	int res=0;
	while(x%2==0){
		res++;
		x/=2;
	}
	return res;
}
int calc5(long long x){
	int res=0;
	while(x%5==0){
		res++;
		x/=5;
	}
	return res;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%Lf",&a[i]);
		num[i]=a[i]*1e9+0.5;
		v1[i]=calc2(num[i])-9;
		v2[i]=calc5(num[i])-9;
	}
	for(int i=n;i>=1;i--){
		for(int j=-v1[i];j<=32;j++){
			for(int k=-v2[i];k<=15;k++){
				ans+=val[j+32][k+15];
			}
		}
		val[v1[i]+32][v2[i]+15]++;
	}
	printf("%lld\n",ans);
	return 0;
}
```