Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Recently, Mr. Frog has learned binary indexed tree. Here is the code of adding t to the interval [1,x]:

If Mr. Frog is required to add t to the interval [l,r], he will add(r,t), and then add(l - 1,-t).

The cost of an interval [l,r] is defined as the number of the “really changed point”. The “really changed point” is the point whose value is modified by the given code.

For example, in order to add 1 to the interval [6,6], Mr. Frog will add 1 to the interval [1,6] (a[6] and a[4] will be added by 1), and add -1 to the interval [1,5] (a[5] and a[4] will be added by -1).

As the result, a[6] will be added by 1, a[5] will be added by -1, and a[4] will be added by 0. a[6] and a[5] are “really changed point”, and the cost is 2.

Mr. Frog wants to calculate the sum of the cost of the interval [l,r]$\subseteq $ [1,n] where l and r are two integers. Help Mr. Frog solve the problem.

void add (int x, int t ){

for (int i = x; i != 0; i -= i & (-i))

a[i] += t;

}

If Mr. Frog is required to add t to the interval [l,r], he will add(r,t), and then add(l - 1,-t).

The cost of an interval [l,r] is defined as the number of the “really changed point”. The “really changed point” is the point whose value is modified by the given code.

For example, in order to add 1 to the interval [6,6], Mr. Frog will add 1 to the interval [1,6] (a[6] and a[4] will be added by 1), and add -1 to the interval [1,5] (a[5] and a[4] will be added by -1).

As the result, a[6] will be added by 1, a[5] will be added by -1, and a[4] will be added by 0. a[6] and a[5] are “really changed point”, and the cost is 2.

Mr. Frog wants to calculate the sum of the cost of the interval [l,r]$\subseteq $ [1,n] where l and r are two integers. Help Mr. Frog solve the problem.

The first line contains only one integer T ($T\leq 10000$), which indicates the number of test cases.

For each test case, it contains an integer n ($1\leq n\leq 10^{18}$).

For each test case, it contains an integer n ($1\leq n\leq 10^{18}$).

提交代码