SP123 PAYING - Paying in Byteland

# 题目翻译 Byteland 有无限多种硬币面额，对于 $i = 0,1,2,\cdots$，第 $i$ 种硬币面额为 $2 ^ i$。我们称一种硬币组合 $(c_1,c_2,\cdots,c_k)$ 是完美的，当且仅当可以使用其中一些来支付 $0$ 到 $c_1 + c_2+ \cdots + c_k$ 之间的每一笔金额（例如硬币组合 $(4,2,2,1)$ 是完美的，而 $(8,1)$ 则不是）。所以问题是，给定一个数字 $n$，请问对于所有面值和为 $n$ 的硬币组合中，硬币数量最少是多少？

第一行输入包含一个整数 $c(c\le 50)$，表示测试样例数。接下来 $c$ 行，每行包含一个整数 $n (n\le10^{1000})$。

对于每个测试样例输出最小数量的硬币。