#include<cstdio>
#include<cmath>
#define For(i,A,B) for(i=(A);i<=(B);++i)
int c[45][20];
inline short Min(short a,short b){return a<b?a:b;}
inline void chkmax(short&a,short b){if(a<b)a=b;}
int main(){
	int n;
	short i,j,maxtwo=0,maxfive=0,two,five;
	long double tm;
	long long x,t,ans=0ll;
	scanf("%d",&n);
	while(n--){
		scanf("%Lf",&tm);t=x=floor(tm*1e9)+0.5;
		for(two=0;!(t&1);t>>=1)++two;
		for(t=x,five=0;!(t%5);t/=5)++five;
		For(i,0,maxtwo)
			For(j,0,maxfive)if(Min(i+two,j+five)>17)ans+=c[i][j];
		++c[two][five];
		chkmax(maxtwo,two);chkmax(maxfive,five);
	}
	printf("%lld\n",ans);
	return 0;
}
### Prompt

Please create a solution in Cpp 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<cmath>
#define For(i,A,B) for(i=(A);i<=(B);++i)
int c[45][20];
inline short Min(short a,short b){return a<b?a:b;}
inline void chkmax(short&a,short b){if(a<b)a=b;}
int main(){
	int n;
	short i,j,maxtwo=0,maxfive=0,two,five;
	long double tm;
	long long x,t,ans=0ll;
	scanf("%d",&n);
	while(n--){
		scanf("%Lf",&tm);t=x=floor(tm*1e9)+0.5;
		for(two=0;!(t&1);t>>=1)++two;
		for(t=x,five=0;!(t%5);t/=5)++five;
		For(i,0,maxtwo)
			For(j,0,maxfive)if(Min(i+two,j+five)>17)ans+=c[i][j];
		++c[two][five];
		chkmax(maxtwo,two);chkmax(maxfive,five);
	}
	printf("%lld\n",ans);
	return 0;
}
```