Binary Indexed Tree 是怎么做的

Question

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

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, and add -1 to the interval 1,5.

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]⊆ [1,n] where l and r are two integers. Help Mr. Frog solve the problem.

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

For each test case, it contains an integer n (1≤n≤1018).

Output
For each test case, output one line ”Case #x: y”, where x is the case number (starting from 1), y is the sum of the cost (modulo 1000000007).

Sample Input
3
1
2
3

Sample Output
Case #1: 1
Case #2: 4
Case #3: 10