#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int cnt[19][19];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    LL ans = 0;
    for(cin >> N; N; N -= 1){
        long double A;
        cin >> A;
        LL X = A * 1000000000 + .5;
        int u = 0, v = 0;
        for(; X % 2 == 0 and u < 18; X /= 2) u += 1;
        for(; X % 5 == 0 and v < 18; X /= 5) v += 1;
        for(int i = 18 - u; i <= 18; i += 1)
            for(int j = 18 - v; j <= 18; j += 1)
                ans += cnt[i][j];
        cnt[u][v] += 1;
    }
    cout << ans;
    return 0;
}
### 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;
using LL = long long;
int cnt[19][19];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    LL ans = 0;
    for(cin >> N; N; N -= 1){
        long double A;
        cin >> A;
        LL X = A * 1000000000 + .5;
        int u = 0, v = 0;
        for(; X % 2 == 0 and u < 18; X /= 2) u += 1;
        for(; X % 5 == 0 and v < 18; X /= 5) v += 1;
        for(int i = 18 - u; i <= 18; i += 1)
            for(int j = 18 - v; j <= 18; j += 1)
                ans += cnt[i][j];
        cnt[u][v] += 1;
    }
    cout << ans;
    return 0;
}
```