問題

錬金術師である Sakky さんは以下のような錬金術を使うことができます．

• $X\times Y$ が偶数であるような $2$ つの整数 $X,Y$ を選び，$X,Y$ を消滅させる代わりに整数 $\frac{X\times Y}2$ を生成する．

$N$ 個の整数 $A_1,A_2,\dots,A_N$ が与えられたとき，Sakky さんは上記の錬金術を最大で何回行うことができるか答えてください．

制約

• 入力はすべて整数
• $1\le N\le 2\times 10^5$
• $1\le A_i\le 10^9$

入力

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

$N$
$A_1\;A_2\;\cdots\;A_N$

出力

答えを整数で出力しなさい．

入出力例

3
3 1 4

2

最初に，$3,4$ に対して錬金術を行い $6$ を生成します．
次に，先ほど生成した $6$ と残りの $1$ に対して錬金術を行い $3$ を生成します．
この時点で残った整数は $3$ の $1$ つだけであるため，これ以上錬金術を行うことはできません．

3
1 2 3

1

最初に，$1,2$ に対して錬金術を行い $1$ を生成します．
残った整数は $1,3$ であり積が偶数ではないため，これ以上錬金術を行うことはできません．

5
1 7 11 13 1001

0

どの $2$ つの数を選んでも積が偶数ではないため，$1$ 回も錬金術を行うことはできません．