#include<iostream>
#include<map>
#include<algorithm>
#include<utility>
using namespace std;
int N;
pair<int,int>A[2<<17];
int cnt[60];
const int off=13;
int main()
{
	cin>>N;
	long ans=0;
	for(int i=0;i<N;i++)
	{
		string S;cin>>S;
		long a=0;
		int b=0;
		bool under=false;
		for(int j=0;j<S.size();j++)
		{
			if(S[j]=='.')
			{
				under=true;
				continue;
			}
			a=a*10+S[j]-'0';
			if(under)b++;
		}
		A[i]=make_pair(-b,-b);
		while(a%2==0)
		{
			A[i].first++;
			a/=2;
		}
		while(a%5==0)
		{
			A[i].second++;
			a/=5;
		}
		if(A[i].first>=0&&A[i].second>=0)ans--;
	}
	sort(A,A+N);
	int j=N-1;
	for(int i=0;i<N;i++)
	{
		while(j>=0&&A[i].first+A[j].first>=0)
		{
			cnt[A[j].second+off]++;
			j--;
		}
		for(int k=0;k<60;k++)
		{
			if(A[i].second+k-off>=0)ans+=cnt[k];
		}
	}
	cout<<ans/2<<endl;
}

### Prompt

In cpp, your task is to solve 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<map>
#include<algorithm>
#include<utility>
using namespace std;
int N;
pair<int,int>A[2<<17];
int cnt[60];
const int off=13;
int main()
{
	cin>>N;
	long ans=0;
	for(int i=0;i<N;i++)
	{
		string S;cin>>S;
		long a=0;
		int b=0;
		bool under=false;
		for(int j=0;j<S.size();j++)
		{
			if(S[j]=='.')
			{
				under=true;
				continue;
			}
			a=a*10+S[j]-'0';
			if(under)b++;
		}
		A[i]=make_pair(-b,-b);
		while(a%2==0)
		{
			A[i].first++;
			a/=2;
		}
		while(a%5==0)
		{
			A[i].second++;
			a/=5;
		}
		if(A[i].first>=0&&A[i].second>=0)ans--;
	}
	sort(A,A+N);
	int j=N-1;
	for(int i=0;i<N;i++)
	{
		while(j>=0&&A[i].first+A[j].first>=0)
		{
			cnt[A[j].second+off]++;
			j--;
		}
		for(int k=0;k<60;k++)
		{
			if(A[i].second+k-off>=0)ans+=cnt[k];
		}
	}
	cout<<ans/2<<endl;
}

```