Description

小明找来了一些数字来问好朋友泽泽，问他如果将这些数字转化成二进制后，会出现多少个1呢。聪明的你能帮泽泽想出解决办法吗？

Input Format

输入两行
第一行是数字n，表示有多少个数字（n<=1000）
第二行是n个数字（这些数字都小于等于10000）

Output Format

共n+1行
前面n行分别表示每个数字转化成二进制数后包含的数字“1”的个数
最后一行表示这些数字转化成二进制后共包含的数字“1”的个数

5
4 35 100 300 1000

1
3
3
4
6
17