#include<bits/stdc++.h>
using namespace std;
const int maxn=60,p=9,maxl=2e5+5;
long long l[maxl];
long long ans=0;
int nx[maxl],ny[maxl];
int a[maxn][maxn];
int n,it=0;
long long read()
{
	long long digit=0;int cnt=0,f=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while((ch<='9'&&ch>='0')||ch=='.')
	{
		if(f) ++cnt;
		if(ch=='.') f=1;
		else digit=10*digit+ch-'0';
		ch=getchar();
	}
	for(int i=1;i<=9-cnt;i++) digit*=10;
	return digit;
}
int main()
{
	memset(nx,0,sizeof(nx));
	memset(ny,0,sizeof(ny));
	memset(a,0,sizeof(a));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		long long x;
		x=read();//printf("%lld\n",x);
		while(x%2==0) ++nx[i],x/=2;
		while(x%5==0) ++ny[i],x/=5;
		++a[nx[i]][ny[i]];
	}
	for(int i=maxn-2;i>=0;i--)
		for(int j=maxn-2;j>=0;j--)
			a[i][j]+=a[i+1][j]+a[i][j+1]-a[i+1][j+1];
	for(int i=1;i<=n;i++)
	{
		ans+=a[max(2*p-nx[i],0)][max(2*p-ny[i],0)];
		if(nx[i]>=p&&ny[i]>=p) --ans;
	}
	printf("%lld\n",ans/2);
	return 0;
}
### Prompt

Please provide a cpp coded solution 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;
const int maxn=60,p=9,maxl=2e5+5;
long long l[maxl];
long long ans=0;
int nx[maxl],ny[maxl];
int a[maxn][maxn];
int n,it=0;
long long read()
{
	long long digit=0;int cnt=0,f=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while((ch<='9'&&ch>='0')||ch=='.')
	{
		if(f) ++cnt;
		if(ch=='.') f=1;
		else digit=10*digit+ch-'0';
		ch=getchar();
	}
	for(int i=1;i<=9-cnt;i++) digit*=10;
	return digit;
}
int main()
{
	memset(nx,0,sizeof(nx));
	memset(ny,0,sizeof(ny));
	memset(a,0,sizeof(a));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		long long x;
		x=read();//printf("%lld\n",x);
		while(x%2==0) ++nx[i],x/=2;
		while(x%5==0) ++ny[i],x/=5;
		++a[nx[i]][ny[i]];
	}
	for(int i=maxn-2;i>=0;i--)
		for(int j=maxn-2;j>=0;j--)
			a[i][j]+=a[i+1][j]+a[i][j+1]-a[i+1][j+1];
	for(int i=1;i<=n;i++)
	{
		ans+=a[max(2*p-nx[i],0)][max(2*p-ny[i],0)];
		if(nx[i]>=p&&ny[i]>=p) --ans;
	}
	printf("%lld\n",ans/2);
	return 0;
}
```