#include<bits/stdc++.h>
#define cs const
using namespace std;
typedef long long ll;
cs int N = 2e5 + 50, M = 70;
int n, c[2][M][M];
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d", &n); ll ans = 0;
	for(int i = 1; i <= n; i++){
		long double y; scanf("%Lf", &y);
		int a = 0, b = 0, typ = -1;
		for(int j = 0; j <= 10; j++) y *= 10, --a;
		ll x = y + 0.01;
		while(x && (x % 10 == 0)) ++a, x /= 10;
		if(x & 1) typ = 1; else typ = 0;
		while(x && (x % 2 == 0)) x >>= 1, ++b;
		while(x && (x % 5 == 0)) x /= 5, ++b;
		for(int j = -10; j <= 10; j++)
		for(int k = 0; k <= 60; k++)
		if(j + a + min(k, b) >= 0)
		ans += c[typ ^ 1][j + 10][k];
		for(int j = -10; j <= 10; j++)
		for(int k = 0; k <= 60; k++)
		if(j + a >= 0)
		ans += c[typ][j + 10][k];
		++c[typ][a + 10][b];
//		cout << ans << " " << a << " " << b << " " << typ << endl;
	} cout << ans; return 0;
}
### Prompt

Your challenge is to write 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<bits/stdc++.h>
#define cs const
using namespace std;
typedef long long ll;
cs int N = 2e5 + 50, M = 70;
int n, c[2][M][M];
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d", &n); ll ans = 0;
	for(int i = 1; i <= n; i++){
		long double y; scanf("%Lf", &y);
		int a = 0, b = 0, typ = -1;
		for(int j = 0; j <= 10; j++) y *= 10, --a;
		ll x = y + 0.01;
		while(x && (x % 10 == 0)) ++a, x /= 10;
		if(x & 1) typ = 1; else typ = 0;
		while(x && (x % 2 == 0)) x >>= 1, ++b;
		while(x && (x % 5 == 0)) x /= 5, ++b;
		for(int j = -10; j <= 10; j++)
		for(int k = 0; k <= 60; k++)
		if(j + a + min(k, b) >= 0)
		ans += c[typ ^ 1][j + 10][k];
		for(int j = -10; j <= 10; j++)
		for(int k = 0; k <= 60; k++)
		if(j + a >= 0)
		ans += c[typ][j + 10][k];
		++c[typ][a + 10][b];
//		cout << ans << " " << a << " " << b << " " << typ << endl;
	} cout << ans; return 0;
}
```