问题描述

当选拔赛正在进行时，学校的办公室装饰有长度为 $N$ 的序列，$a=\{a_1,a_2,a_3,...,a_N\}$。光头强是一名员工，他想玩这个序列。

具体来说，他希望尽可能多地重复以下操作:

对于满足 $1\leq i\leq N$ 的每个 $i$，执行以下操作之一：

• 将 $a_i$ 除以 2，
• 将 $a_i$ 乘以 3。

这里，不允许对每个 $i$ 都选择将 $a_i$ 乘以 3，并且运算后的 $a_i$ 的值必须是整数。

最多可以做多少次操作？

数据规模

$N$ 为 $1$ 至 $10000$（含）之间的整数。

$a_i$ 是 $1$ 至 $1000000000$（含）之间的整数。

输入

输入由标准输入按以下格式给出:

$N$

$a_1\ a_2\ a_3\ ...\ a_N$

输出

打印光头强可以执行的最大操作数。

3
5 2 4

3

序列最初是 $\{5,2,4\}$。可以执行三个操作，如下所示:

• 首先，将 $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