To be or not to be? - that is the question...

Hamlet - Prince of Denmark

Ruslan dreams to become a millionaire, and for this, in his opinion, he should become Bill Gates, oh, a programmer ...

To achieve this goal, he is engaged in solving programming problems at any convenient (and not so) time. So, if there is now some unimportant (from his point of view) or not interesting lesson, Ruslan asks to leave the classroom, and in the corridor he takes out his old mobile phone connected to the Internet and starts solving problems. And today, as usual, he started coding in class, but it's bad - there is not enough memory on the mobile phone, and the numbers in the task are not only big, but there are a lot of them.

And the problem is very simple: "_Calculate among the given integers the number of those that are a power of two_".

Help Ruslan to make another step to reach the goal to become a millionaire in the future!

Input

First line contains the number of integers n (1 ≤ n ≤ 106), second line contains n integers. All numbers in the second line are positive and do not exceed 18446744073709551615.

Output

Print the number of integers that are a power of two.