Description

Jrahc has developed a jewel-breaking game. In this game, you can process diamonds by striking them with a chosen force.

Specifically, for a diamond of size $x$, you may choose a positive integer $y < x$. According to the game's rules, the diamond will disappear, and for each divisor $z$ of $y$, a diamond of size $z$ will be generated with probability $\frac{z}{y}$.

In particular, diamonds of size $1$ cannot be struck.

Clearly, this game may violate the law of conservation of matter. After being criticized by Coinred, Jrahc refused to change the code and instead posed a game theory challenge to him:

Suppose there are several diamonds in the game. We take turns processing them, with me going first. On each turn, you must strike the largest diamond currently present. If all diamonds are of size 1, the player who cannot make a move loses. What is my probability of winning if we both play optimally?

Coinred must correctly answer this question to convince Jrahc to change his game, but he is not good at game theory—so he has come to you for help.

Format

Input

The first line contains one integer $n\,(1\leq n\leq 110)$, the number of diamonds.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n\,(1\leq a_i\leq 110)$, the sizes of the diamonds.

Output

One rational number, representing the probability of winning, formatted to six decimal places.

Samples

2
1 2

1.000000

2
2 2

0.000000