Binary Indexed Tree

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] (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, output one line ”Case #x: y”, where x is the case number (starting from 1), y is the sum of the cost (modulo 1000000007).

3
1
2
3

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