*3 或 /2

题目描述

随着 AtCoder Beginner Contest 100 的举办,AtCoder 公司将装饰一个长度为 $N$ 的数列 $a =${$a_1, a_2, a_3, ..., a_N$}。

员工 Snuke 君想用这个数列玩一玩。

具体来说,他打算尽可能多地重复以下操作。

对满足 $1 \leq i \leq N$ 的所有 $i$,分别执行「将 $a_i$ 的值除以 $2$」「将 $a_i$ 的值乘以 $3$」两者之一。

但是,不能对所有的 $i$ 都乘以 $3$,并且操作后 $a_i$ 的值必须是整数。

请找出最多能进行多少次操作。

输入格式

输入按以下格式从标准输入给出。

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

输出格式

输出 Snuke 君最多能进行的操作次数。

样例

3
5 2 4

3

最初数列为 ${5, 2, 4}$,按如下方式操作可以进行 $3$ 次操作。

• 首先,将 $a_1$ 乘以 $3$,将 $a_2$ 乘以 $3$,将 $a_3$ 除以 $2$。于是数列变为 ${15, 6, 2}$。
• 接着,将 $a_1$ 乘以 $3$,将 $a_2$ 除以 $2$,将 $a_3$ 乘以 $3$。于是数列变为 ${45, 3, 6}$。
• 最后,将 $a_1$ 乘以 $3$,将 $a_2$ 乘以 $3$,将 $a_3$ 除以 $2$。于是数列变为 ${135, 9, 3}$。

4
631 577 243 199

0

由于所有元素都是奇数,无法进行操作。因此答案为 $0$。

10
2184 2126 1721 1800 1024 2528 3360 1945 1280 1776

39

数据范围

• $N$ 是不小于 $1$ 且不超过 $10 \ 000$ 的整数
• $a_i$ 是不小于 $1$ 且不超过 $1 \ 000 \ 000 \ 000$ 的整数