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

const int MAX = 50;

//2D cumulative sum(座標は1-indexedであることに注意せよ)
int64_t sum[MAX][MAX];



int main(){
  int64_t N;
  cin >> N;
  vector<int64_t> vec(N);
  for(int i=0; i<N; i++){
    long double x;
    cin >> x;
    x *= 1e9;
    vec[i] = round(x);
  }
  
  vector<int> T(N);
  vector<int> F(N);
  
  //掛け算して10^18 = 2^18 * 5^18で割れれば良い
  
  for(int i=0; i<N; i++){
    int two = 0;
    int five = 0;
    int64_t x = vec[i];
    while(x %2 == 0){
      x /= 2;
      two++;
    }
    while(x %5 == 0){
      x /= 5;
      five++;
    }
    T[i] = two;
    F[i] = five;
    sum[two][five]++;
  }
  
  
  int64_t ans = 0;
  
  for(int i=0; i<N; i++){
    int64_t x = vec[i];
    for(int j=max(0,18-T[i]); j<MAX; j++){
      for(int k=max(0,18-F[i]); k<MAX; k++){
        ans += sum[j][k];
        if(j == T[i] && k == F[i]){
          ans--;
        }
      }
    }
  }
  
  cout << ans / 2 << endl;
  
}
### Prompt

Please provide a cpp coded solution 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;

const int MAX = 50;

//2D cumulative sum(座標は1-indexedであることに注意せよ)
int64_t sum[MAX][MAX];



int main(){
  int64_t N;
  cin >> N;
  vector<int64_t> vec(N);
  for(int i=0; i<N; i++){
    long double x;
    cin >> x;
    x *= 1e9;
    vec[i] = round(x);
  }
  
  vector<int> T(N);
  vector<int> F(N);
  
  //掛け算して10^18 = 2^18 * 5^18で割れれば良い
  
  for(int i=0; i<N; i++){
    int two = 0;
    int five = 0;
    int64_t x = vec[i];
    while(x %2 == 0){
      x /= 2;
      two++;
    }
    while(x %5 == 0){
      x /= 5;
      five++;
    }
    T[i] = two;
    F[i] = five;
    sum[two][five]++;
  }
  
  
  int64_t ans = 0;
  
  for(int i=0; i<N; i++){
    int64_t x = vec[i];
    for(int j=max(0,18-T[i]); j<MAX; j++){
      for(int k=max(0,18-F[i]); k<MAX; k++){
        ans += sum[j][k];
        if(j == T[i] && k == F[i]){
          ans--;
        }
      }
    }
  }
  
  cout << ans / 2 << endl;
  
}
```