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

见题面

见题面