#include<bits/stdc++.h>
using namespace std;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i,n) for(int i=0; i<(n); i++)

int N;

LL X[19][19] = {};

int main() {

 scanf("%d",&N);
 rep(i,N){
  double buf; scanf("%lf",&buf);
  LL a = buf * 1.0e9 + 0.5;
  int idx2 = 0, idx5 = 0;
  while(a%2==0){ idx2++; a/=2; }
  while(a%5==0){ idx5++; a/=5; }
  X[min(idx2,18)][min(idx5,18)]++;
 }

 LL ans=0;
 rep(x,19)rep(y,19)rep(xx,19)rep(yy,19){
  if(x+xx < 18) continue;
  if(y+yy < 18) continue;
  if(x==xx && y==yy)
   ans += X[x][y]*(X[x][y]-1);
  else
   ans += X[x][y]*X[xx][yy];
 }

 ans /= 2;
 printf("%lld\n",ans);
 
 return 0;
}
### Prompt

Construct a cpp code solution to the problem outlined:

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;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i,n) for(int i=0; i<(n); i++)

int N;

LL X[19][19] = {};

int main() {

 scanf("%d",&N);
 rep(i,N){
  double buf; scanf("%lf",&buf);
  LL a = buf * 1.0e9 + 0.5;
  int idx2 = 0, idx5 = 0;
  while(a%2==0){ idx2++; a/=2; }
  while(a%5==0){ idx5++; a/=5; }
  X[min(idx2,18)][min(idx5,18)]++;
 }

 LL ans=0;
 rep(x,19)rep(y,19)rep(xx,19)rep(yy,19){
  if(x+xx < 18) continue;
  if(y+yy < 18) continue;
  if(x==xx && y==yy)
   ans += X[x][y]*(X[x][y]-1);
  else
   ans += X[x][y]*X[xx][yy];
 }

 ans /= 2;
 printf("%lld\n",ans);
 
 return 0;
}
```