Description

大力士到公园锻炼，他发现公园里出现了一些有趣的石子，这些石子间存在以下规律：

一：任意两个石子之间的质量不同；

二：对于任意一个石子总是存在另一个石子的质量是它的二倍。

现在设质量最轻的石子质量为1千克，大力士为了向众人炫耀自己的力量很大，他决定要挑战自己力量上限。已知大力士最多能举起质量为m千克。大力士想请你帮它算一下他要举多少石子才能挑战成功。大力士通过挑战的条件为他举起的石子质量总和恰好等于m。

Input Format

第一行输入一个整数T（1≤T<100）表示测试样例数。

对于每组样例在一行输入一个整数m(1≤m≤1000000000)，即表示大力士最多能举起质量为m千克。

Output Format

对于每组样例在一行输出一个整数，表示大力士需要举起石头的数量。

1
6

2

Hint

对于 6千克的重量，大力士举起重量为 2千克和 4千克的石头，总重量恰好为 6千克，即 2 块石头。

Source

1816 Online Judge 10.100.0.232