#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e5+5;

int n;
LL a[90][40];
LL ans;

int main()
{
	cin>>n;
	while(n--)
	{
		string s;
		cin>>s;
		LL y=0;
		int u=s.size();
		for(int i=0;i<s.size();i++)
			if(s[i]=='.') u=i;
		if(u==s.size()) s+=".";
		for(int i=s.size()-u;i<=9;i++) s+="0";
		for(int i=0;i<s.size();i++)
			if(s[i]!='.') y=y*10+s[i]-'0';
		int z1=0,z2=0;
		while(y%2==0) y/=2,z1++;
		while(y%5==0) y/=5,z2++;
		a[z1+36][z2+11]++;
	}
	for(int i=0;i<90;i++)
	for(int j=0;j<40;j++)
	for(int k=90-i;k<90;k++)
	for(int l=40-j;l<40;l++)
		ans+=a[i][j]*a[k][l];
	for(int i=45;i<90;i++)
	for(int j=20;j<40;j++)
		ans-=a[i][j];
	cout<<ans/2<<'\n';
	
	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;
#define LL long long
const int N=2e5+5;

int n;
LL a[90][40];
LL ans;

int main()
{
	cin>>n;
	while(n--)
	{
		string s;
		cin>>s;
		LL y=0;
		int u=s.size();
		for(int i=0;i<s.size();i++)
			if(s[i]=='.') u=i;
		if(u==s.size()) s+=".";
		for(int i=s.size()-u;i<=9;i++) s+="0";
		for(int i=0;i<s.size();i++)
			if(s[i]!='.') y=y*10+s[i]-'0';
		int z1=0,z2=0;
		while(y%2==0) y/=2,z1++;
		while(y%5==0) y/=5,z2++;
		a[z1+36][z2+11]++;
	}
	for(int i=0;i<90;i++)
	for(int j=0;j<40;j++)
	for(int k=90-i;k<90;k++)
	for(int l=40-j;l<40;l++)
		ans+=a[i][j]*a[k][l];
	for(int i=45;i<90;i++)
	for(int j=20;j<40;j++)
		ans-=a[i][j];
	cout<<ans/2<<'\n';
	
	return 0;
}
```