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

// ----------- define --------------
#define int long long
#define vi vector<int>
#define vc vector<char>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define all(x) (x).begin(),(x).end()
#define get_bit(x, k) ((x >> k) & 1)
// ---------------------------------

void MAIN() {
  int n;
  cin >> n;
  int ans = 0;
  map<pair<int, int>, int> m;
  for (int i = 0; i < n; i++) {
    double _; cin >> _;
    int t = llround(_ * 1e9);
    int ct = 0, cf = 0;
    while (t % 2 == 0) {
      t /= 2;
      ct++;
    }
    while (t % 5 == 0) {
      t /= 5;
      cf++;
    }
    for (auto &j : m) {
      if (j.fi.fi + ct >= 18 && j.fi.sc + cf >= 18) {
        ans += j.sc;
      }
    }
    m[ii(ct, cf)]++;
  }
  cout << ans << '\n';
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}

### Prompt

Develop a solution in CPP 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 --------------
#define int long long
#define vi vector<int>
#define vc vector<char>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define all(x) (x).begin(),(x).end()
#define get_bit(x, k) ((x >> k) & 1)
// ---------------------------------

void MAIN() {
  int n;
  cin >> n;
  int ans = 0;
  map<pair<int, int>, int> m;
  for (int i = 0; i < n; i++) {
    double _; cin >> _;
    int t = llround(_ * 1e9);
    int ct = 0, cf = 0;
    while (t % 2 == 0) {
      t /= 2;
      ct++;
    }
    while (t % 5 == 0) {
      t /= 5;
      cf++;
    }
    for (auto &j : m) {
      if (j.fi.fi + ct >= 18 && j.fi.sc + cf >= 18) {
        ans += j.sc;
      }
    }
    m[ii(ct, cf)]++;
  }
  cout << ans << '\n';
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}

```