说明

总所周知，乔斯币具有丰富的收藏价值，并且还能用来兑换精美的小礼品。
经过长时间的努力，乔斯的小朋友们都积累了一定的积分值，终于到了兑换乔斯币的日子了（欢呼！！！）
已知即将给 $n$个小朋友兑换乔斯币，每个小朋友的积累的积分值为 $p_{i}$， 乔斯准备了不同种类面值的乔斯币，它们的面值分别是1，2，4，8，16……（即都为2的幂次）。小朋友们将得到和自己积分值等价的一些乔斯币，并且每个小朋友同一种类的乔斯币只能得到一个。
现在请你算出，每个小朋友将获得多少个乔斯币呢。

输入格式

第一行输入一个数 $n$ $(2 \le n \le 10^5)$，表示将要兑换乔斯币的小朋友的数量。
之后 $n$ 行，每行对应一个数 $p_{i}$ ，范围是$(1 \le p_{i} \le 10^9)$，分别表示每个小朋友的积分值。

输出格式

输出 $n$ 行，每行一个整数，表示每个小朋友得到的乔斯币的数量。

样例

3
15
1
22

4
1
3