#20996. 乘3还是除以2

乘3还是除以2

Description

有一个长度为 NN1N100001 \leq N \leq 10000)的数组 aa1ai1091 \leq a_i \leq 10^9),要尽可能多地重复以下操作

对于每一个满足 1iN1 \leq i \leq Nii,执行以下之一:1.将 a[i]a[i] 乘以 33,2. 将 a[i]a[i] 除以 22

且不能全部都选择乘以 33 (至少有一个除以 22 的操作)另外,操作后的数必须为整数。

问最多能做多少次操作

Format

Input

第一行一个整数 NN

第二行 NN 个空格隔开的整数代表 aia_i

Output

输出一个整数

Samples

3
5 2 4
3

Hint

能够进行三次操作:

  1. a[i]3a[2]3a[3]/2a[i]*3,a[2]*3,a[3]/2,数组变成了 15,6,215,6,2
  2. a[i]3a[2]/2a[3]3a[i]*3,a[2]/2,a[3]*3,数组变成了 45,3,645,3,6
  3. a[i]3a[2]3a[3]/2a[i]*3,a[2]*3,a[3]/2,数组变成了 135,9,3135,9,3