Start: Oct, 25, 2016 18:02:00
2016秋程序设计通识课第二次考试
End: Oct, 26, 2016 11:05:00
Time elapsed:
Time remaining:

分硬币 2051

Time Limit:  1 s      Memory Limit:   128 MB
Submission:28     AC:6     Score:1

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