526互联

Sum in Binary Tree

发布时间 2023-07-11 15:42:54作者: o-Sakurajimamai-o
Sum in Binary Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vanya really likes math. One day when he was solving another math problem, he came up with an interesting tree. This tree is built as follows.

Initially, the tree has only one vertex with the number 11 — the root of the tree. Then, Vanya adds two children to it, assigning them consecutive numbers — 22 and 33, respectively. After that, he will add children to the vertices in increasing order of their numbers, starting from 22, assigning their children the minimum unused indices. As a result, Vanya will have an infinite tree with the root in the vertex 11, where each vertex will have exactly two children, and the vertex numbers will be arranged sequentially by layers.

Part of Vanya's tree.

Vanya wondered what the sum of the vertex numbers on the path from the vertex with number 1 to the vertex with number n in such a tree is equal to. Since Vanya doesn't like counting, he asked you to help him find this sum.

Input

The first line contains a single integer t (1≤t≤104) — the number of test cases.

This is followed by t lines — the description of the test cases. Each line contains one integer n (1≤n≤10161≤≤1016) — the number of vertex for which Vanya wants to count the sum of vertex numbers on the path from the root to that vertex.

Output

For each test case, print one integer — the desired sum.

Example
input
Copy
6
3
10
37
1
10000000000000000
15
output
Copy
4
18
71
1
19999999999999980
26
Note

In the first test case of example on the path from the root to the vertex 33 there are two vertices 11 and 33, their sum equals 44.

In the second test case of example on the path from the root to the vertex with number 1010 there are vertices 11, 22, 55, 1010

sum of their numbers equals 1+2+5+10=181+2+5+10=18.

// //Sum in Binary Tree
//一个函数 向上搜索就行
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
int dfs(int x)
{
    if(x==1||x==0) return 1;
    else return x+dfs(x/2);
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        res=dfs(n); 
        cout<<res<<endl;
    }
    return 0;
}