Alice có một số nguyên dương \(x\). Cô ấy có thể thực hiện thao tác xóa bit 1 thấp nhất: \(x = x \ \& \ (x - 1)\). Cho dãy gồm \(N\) số nguyên, hãy đếm tổng số thao tác cần thực hiện để biến tất cả các số trong dãy thành 0.

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N $\le 10^5\)).
• Dòng 2: \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i $\le 10^9\)).

Định dạng đầu ra

• In ra tổng số thao tác cần thực hiện.

Ví dụ

Input:

3
13 7 4

Output:

7

Giải thích: Số 13 (\(1101_2\)) cần 3 bước, số 7 (111_2) cần 3 bước, số 4 (100_2) cần 1 bước \(\implies\) tổng là \(3 + 3 + 1 = 7\).

Ràng buộc & Subtasks