Alice yêu thích các con số. Cô ấy muốn biết tổng số lượng bit 1 trong biểu diễn nhị phân của tất cả các số trong một dãy số gồm \(N\) phần tử.

Ví dụ: số \(13\) có biểu diễn nhị phân là \(1101_2\), có đúng 3 bit 1.

Đị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 \(a_1, a_2, \dots, a_N\) (\(1 \le a_i $\le 10^9\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng số lượng bit 1 của tất cả các số trong dãy.

Ví dụ

Input:

4
3 5 7 13

Output:

10

Giải thích: \(3=11_2\) (2 bit), \(5=101_2\) (2 bit), \(7=111_2\) (3 bit), \(13=1101_2\) (3 bit) \(\implies\) tổng \(= 2 + 2 + 3 + 3 = 10\).

Ràng buộc & Subtasks