問題文

$N$個の要素からなる数列$A$が与えられます。$i$番目($1\le i\le N$)の要素は$A_i$です。この数列の空ではない部分列を考えます。
ここで部分列とは「数列の要素を$0$個以上いくつか選んで削除し、残ったものを元の順序を保って並べた数列」を表します。
含まれる全ての要素の最大公約数が$1$となるような数列$A$の部分列の総数を求めてください。

ある2つの部分列に関して、その要素の値が全て一致しても元の数列における要素が異なるものが含まれている場合、その部分列は異なるものとして扱うことに注意してください。

入力

$N$
$A_1{A}_2\dots A_N$

入力は全て整数である
$1\le N\le 50$
$1\le A_i\le {10}^8(1\le i\le N)$

出力

最後に改行してください。

サンプル

3
1 2 3

5

4
1 1 1 1

15

4
2 4 8 16

0

10
801754 703742 332182 68016 914814 8470 937255 293192 313080 501971

763