問題文

高橋くんは魔法の箱を持っています。

この箱に整数を入れるとそれに対応した整数が出てきます。

出てくる整数は入れた整数だけによって決まり、同じ整数を入れると毎回同じ結果が得られます。

高橋くんは任意の整数 $x$ について、$x$ を入れた時と $2x$ を入れた時に出てくる整数が同じであることに気づきました。

高橋くんが入れた整数が $N$ 個与えられるので、最大で何種類の整数が出てくるか答えてください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $a_2$ .. $a_N$

• $1$ 行目には、高橋くんが箱に入れる整数の個数 $N ( 1 ≦ N ≦ 10^5)$ が与えられる。
• $2$ 行目には、高橋くんが箱に入れる $N$ 個の整数が空白を区切りとして与えられる。
• $1 ≦ a_i ≦ 10^9 ( 1 ≦ i ≦ N)$ であることが保証される。
• $i ≠ j$ のとき、$a_i ≠ a_j$ であることが保証される。

出力

最大で何種類の整数が出てくるかを標準出力に出力せよ。

末尾の改行を忘れないこと。

部分点

この問題には部分点が設定されている。

• $20$ 点分のテストケースにおいて、$1 ≦ N ≦ 3,000$ を満たす。
• 別の $30$ 点分のテストケースにおいて、$1 ≦ a_i ≦ 5\*10^5 ( 1 ≦ i ≦ N)$ を満たす。

入力例1

3
1 2 3

出力例1

2

$2$ を入れた時に出てくる整数は、$1$ を入れた時に出てくる整数と等しいので、最大で $2$ 種類の整数が出てきます。

入力例2

4
2 4 8 16

出力例2

1

すべて同じ整数が出てきます。

入力例3

4
2 3 5 7

出力例2

4

出てくる整数が全て違う可能性があります。