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

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

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

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

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

样例 输入复制 3 15 1 22 输出复制 4 1 3 提示 对于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； 样例中，

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

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

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