#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int cnt[35][35];

int main() {
	unsigned long long ans = 0;
	int n; scanf("%d", &n);
	for(int i=1;i<=n;i++) {
		long double x; cin >> x;
		long double y = x; for(int j=1;j<=10;j++) y *= 10;
		unsigned long long p = (unsigned long long)(y + 0.5);
		int c2 = 0, c5 = 0;
		while( p % 2 == 0 ) p /= 2, c2++;
		while( p % 5 == 0 ) p /= 5, c5++;
		c2 = min(c2, 30), c5 = min(c5, 30), cnt[c2][c5]++;
		if( (unsigned long long)(x * x) == x * x ) ans--;
	}
	
	for(int i=0;i<=30;i++) for(int j=0;j<=30;j++)
	for(int p=0;p<=30;p++) for(int q=0;q<=30;q++)
		if( i + p >= 20 && j + q >= 20 && cnt[i][j] && cnt[p][q] )
			ans += 1ull * cnt[i][j] * cnt[p][q];
	
	printf("%llu\n", ans / 2);
}
### Prompt

Generate a cpp solution to 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 <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int cnt[35][35];

int main() {
	unsigned long long ans = 0;
	int n; scanf("%d", &n);
	for(int i=1;i<=n;i++) {
		long double x; cin >> x;
		long double y = x; for(int j=1;j<=10;j++) y *= 10;
		unsigned long long p = (unsigned long long)(y + 0.5);
		int c2 = 0, c5 = 0;
		while( p % 2 == 0 ) p /= 2, c2++;
		while( p % 5 == 0 ) p /= 5, c5++;
		c2 = min(c2, 30), c5 = min(c5, 30), cnt[c2][c5]++;
		if( (unsigned long long)(x * x) == x * x ) ans--;
	}
	
	for(int i=0;i<=30;i++) for(int j=0;j<=30;j++)
	for(int p=0;p<=30;p++) for(int q=0;q<=30;q++)
		if( i + p >= 20 && j + q >= 20 && cnt[i][j] && cnt[p][q] )
			ans += 1ull * cnt[i][j] * cnt[p][q];
	
	printf("%llu\n", ans / 2);
}
```