HZNUOJ

分硬币

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:545     AC:186     Score:89.41

Description

CYP学长经过千辛万苦,终于把我们校的OJ升级到了2.0版,作为奖赏,单总把他儿时珍藏的一大堆硬币(没错,游戏币)送给了学长。

但这些硬币杂乱无章堆在一块,有强迫症的CYP学长不能忍,决定把它们分成一枚一枚的。

已知一共有n枚硬币,CYP学长每次会把硬币对半分,如果是奇数,则其中一份多一个,然后对分出来的两堆硬币做相同的操作,直到分成一枚为止。每次把一堆硬币分成两堆,消耗的体力是分成的两堆的硬币数之和。

现在给你总硬币数n,请输出消耗的总体力。

Input

本题有多组输入

第一行一个整数T,代表输入组数

每组数据有一个整数n(0<=n<=10^5)

Output

对每组数据,输出一个整数,代表消耗的体力总数

Samples

input
3 1 2 3
output
0 2 5

Author

WEI, Lixin