Problem Statement

Có một dãy số ~N~ , ~a = ~ { ~a_1, a_2, a_3, ..., a_N~ }.
Aquarius muốn chơi đùa cùng dãy số này

Được biết cậu ấy có thể thực hiện phép tính sau bao nhiêu lần tùy thích:

Với mỗi vị trí ~i~ thuộc ~1 \leq i \leq N~ , Bạn có thể thực hiện các phép tính sau: "chia ~a_i~ cho ~2~ " hoặc "Nhân ~a_i~ cho ~3~ "

sao cho với mỗi ~i~ trong dãy đều phải có cả 2 phép tính

Thay vì như bao bài toán khác lần này Aquarius quyết định xử lý phức tạp hơn, cậu ấy tự hỏi có thể làm dãy số trên trở nên lẻ nhiều nhất bao nhiêu phép tính?

Thay vì ít nhất :333

Constraints

• ~N~ là một số nguyên thuộc ~1~ và ~10 \ 000~
• ~a_i~ là một số nguyên thuộc ~1~ và ~1 \ 000 \ 000 \ 000~

Input

Đầu vào được mô tả như sau:

~N~

~a_1~ ~a_2~ ~a_3~ ~...~ ~a_N~

Output

In số lượng phép tính nhiều nhất mà cậu ta có thể thực hiện

Sample Input 1

3
5 2 4

Sample Output 1

3

Chuỗi ban đầu là ~ {5, 2, 4} ~. Ba hoạt động có thể được thực hiện như sau:

• Đầu tiên, nhân ~ a_1 ~ với ~ 3 ~, nhân ~ a_2 ~ với ~ 3 ~ và chia ~ a_3 ~ cho ~ 2 ~. Trình tự bây giờ là ~ {15, 6, 2} ~.
• Tiếp theo, nhân ~ a_1 ~ với ~ 3 ~, chia ~ a_2 ~ với ~ 2 ~ và nhân ~ a_3 ~ với ~ 3 ~. Trình tự bây giờ là ~ {45, 3, 6} ~.
• Cuối cùng, nhân ~ a_1 ~ với ~ 3 ~, nhân ~ a_2 ~ với ~ 3 ~ và chia ~ a_3 ~ cho ~ 2 ~. Trình tự bây giờ là ~ {135, 9, 3} ~.

Sample Input 2

4
631 577 243 199

Sample Output 2

0

Sample Input 3

10
2184 2126 1721 1800 1024 2528 3360 1945 1280 1776

Sample Output 3

39