Odd Mathematics
Problem
Mandark thinks he is better than Dexter. He challenges Dexter to find answer to a mathematics problem he created. Dexter accepts the challenge and decides to write a program for it to reduce manual calculations.
The problem: Let f(x) be the greatest odd divisor of x, where x is a positive integer. You are given a positive integer X. Calculate f(1)+f(2)+...+f(X).
INPUT
First line of input gives T, the number of test cases. T lines follow, each having X as input positive integer.
OUTPUT
Print value of f(1)+f(2)+...+f(X) for each test case.
CONSTRAINTS
- 1 <= T <= 50
- X will be between 1 and 1000000000, inclusive.
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
For first case, f(1)+f(2)+f(3)+f(4)+f(5)+f(6)+f(7)=1+1+3+1+5+3+7=21
Similarly, f(1)+f(2)+...+f(777) = 201537
Contributers:
Gaurav Agarwal
