小泽得到一个长度为 $N$ 的正整数序列。一次操作中，他必须对每个位置分别选择“除以 $2$”或“乘以 $3$”，但不能让所有位置都选择乘以 $3$；同时，操作后的每个数都必须仍是整数。

只要操作仍然可行，小泽就希望继续。请计算最多能够完成多少次操作。

输入格式

第一行包含整数 $N$。第二行包含 $N$ 个正整数 $a_1,a_2,\ldots,a_N$。

输出格式

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

3
5 2 4

3

4
631 577 243 199

0

10
2184 2126 1721 1800 1024 2528 3360 1945 1280 1776

39

数据范围

• $1\le N\le10^4$
• $1\le a_i\le10^9$