历经旷日持久的战争之后，百纳瑞王国（The Kingdom of Binary）终于迎来了胜利的曙光。于是国王决定在胜利日这一天为在战争中奋战的将领们授勋。
已经需要为N位将领授勋，他们每人有一个功勋值 $p_i$。国王准备了不同种类的勋章，它们分别代表 $1,\ 2,\ 4,\ 8,\ 16,\ \dots$（即 $2$ 的幂次）的功勋值。国王将用与每位将领功勋值对等数值的勋章授予他们，并且每位将领只会被授予一枚同种勋章。
现在请你帮助国王算出，对于每一位将领，他需要准备多少枚勋章？

第一行输入一个数 $N\ (2 \leq N \leq 100,000)$，表示将领人数；
之后 $N$ 行，每行输入一个数，分别表示每位将领的功勋值。$1 \leq p_i \leq 10^9$。

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