#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=200000,M=50;

int n;
LL a[N+9];
int c[N+9][2];
int cnt[M+9][M+9];

void work(){
  scanf("%d",&n);
  for (int i=1;i<=n;++i){
	double x;
	scanf("%lf",&x);
	a[i]=(LL)(1000000000.0*x+0.5);
	for (;a[i]&1^1;a[i]>>=1) ++c[i][0];
	for (;a[i]%5==0;a[i]/=5) ++c[i][1];
  }
  LL ans=0;
  for (int i=1;i<=n;++i){
	int x=max(18-c[i][0],0),y=max(18-c[i][1],0);
	for (int j=x;j<=M;++j)
	  for (int k=y;k<=M;++k) ans+=cnt[j][k];
    ++cnt[c[i][0]][c[i][1]];
  }
  printf("%lld\n",ans);
}

int main(){
  int T=1;
  //scanf("%d",&T);
  for (;T--;) work();
  return 0;
}
### 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<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=200000,M=50;

int n;
LL a[N+9];
int c[N+9][2];
int cnt[M+9][M+9];

void work(){
  scanf("%d",&n);
  for (int i=1;i<=n;++i){
	double x;
	scanf("%lf",&x);
	a[i]=(LL)(1000000000.0*x+0.5);
	for (;a[i]&1^1;a[i]>>=1) ++c[i][0];
	for (;a[i]%5==0;a[i]/=5) ++c[i][1];
  }
  LL ans=0;
  for (int i=1;i<=n;++i){
	int x=max(18-c[i][0],0),y=max(18-c[i][1],0);
	for (int j=x;j<=M;++j)
	  for (int k=y;k<=M;++k) ans+=cnt[j][k];
    ++cnt[c[i][0]][c[i][1]];
  }
  printf("%lld\n",ans);
}

int main(){
  int T=1;
  //scanf("%d",&T);
  for (;T--;) work();
  return 0;
}
```