大数 popcount

题目描述

在位运算相关的题目中，$\operatorname{popcount}(n)$ 是一个很重要的函数。对于给定的非负整数 $n$，$\operatorname{popcount}(n)$ 返回 $n$ 的二进制表示中 $1$ 的个数。

例如，$299$ 的二进制表示为 $(299)_2 = 100101011$，因此 $\operatorname{popcount}(299) = 5$。

现在有 $q$ 次询问，每次询问会给出一个非负整数 $n$，你需要计算 $\operatorname{popcount}(n)$ 的值。

输入格式

第一行一个正整数 $q$（$1 \leq q \leq 1,000$），表示询问的个数。

接下来的 $q$ 行，每行一个非负整数 $n$（$1 \leq n \leq 10^{1000}$）。

保证所有 $n$ 在十进制表示中的长度之和不超过 $5,000$，且不存在前导零。

输出格式

对于每个询问，输出一行一个整数 $\operatorname{popcount}(n)$。

样例输入

4
2
7
299
1112345678999

样例输出

1
3
5
20

Author：廖纪童