Problem Statement

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

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

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

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

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

Input

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

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$ であることが保証される。

Output

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

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

部分点

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

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