历经旷日持久的战争之后，百纳瑞王国（The Kingdom of Binary）终于迎来了胜利的曙光。于是国王决定在胜利日这一天为在战争中奋战的将领们授勋。

已经需要为N位将领授勋，他们每人有一个功勋值p[i]。国王准备了不同种类的勋章，它们分别代表1,2,4,8,16......（即2的幂次）的功勋值。国王将用与每位将领功勋值对等数值的勋章授予他们，并且每位将领只会被授予一枚同种勋章。

现在请你帮助国王算出，对于每一位将领，他需要准备多少枚勋章？

收起

输入

第一行输入一个数N，表示将领人数；
之后N行，每行输入一个数，分别表示每位将领的功勋值。

输出

输出N行，每行一个数表示需要授予该将领的勋章数。

数据范围

对于20%的数据，2≤N≤10，1≤p[i]≤200；
对于50%的数据，2≤N≤1000，1≤p[i]≤500000；
对于100%的数据，2≤N≤100000，1≤p[i]≤10^9；

输入样例

3
15
1
22

输出样例

4
1
3

样例解释

样例中，

第一位将领功勋值为15，授予8,4,2,1，共4枚勋章；

第二位将领功勋值为1，授予1，共1枚勋章；

第三位将领功勋章为22，授予16,4,2，共3枚勋章。

------------------------------------------------------------------------------------

解答：由于组成勋章的权值都是 2 的幂，因此问题转为求每个数的二进制表示中，有多少个 1。