#include<stdio.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
static inline int max(const int x,const int y){return x>y?x:y;}
int main(void)
{
  int ten[21][21]={{0}},N;long count=0;long double A;
  if(!scanf("%d",&N))return -1;
  rep(i,N)
  {
    if(!scanf("%Lf",&A))return -1;
    long x=1l*1e9*A+0.1;int even=0,five=0;
    while(!(x&1)&&even<=18){x/=2,even++;}
    while(x%5==0&&five<=18){x/=5,five++;}
    for(int j=max(0,18-even);j<=20;j++)for(int k=max(0,18-five);k<=20;k++)count+=ten[j][k];
    ten[even][five]++;
  }
  return printf("%ld\n",count),0;
}
### Prompt

Create a solution in Cpp for 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<stdio.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
static inline int max(const int x,const int y){return x>y?x:y;}
int main(void)
{
  int ten[21][21]={{0}},N;long count=0;long double A;
  if(!scanf("%d",&N))return -1;
  rep(i,N)
  {
    if(!scanf("%Lf",&A))return -1;
    long x=1l*1e9*A+0.1;int even=0,five=0;
    while(!(x&1)&&even<=18){x/=2,even++;}
    while(x%5==0&&five<=18){x/=5,five++;}
    for(int j=max(0,18-even);j<=20;j++)for(int k=max(0,18-five);k<=20;k++)count+=ten[j][k];
    ten[even][five]++;
  }
  return printf("%ld\n",count),0;
}
```