Binary Indexed Tree

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

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

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] (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.

Input

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}$).

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

Hint

wange2014

Source

2016中国大学生程序设计竞赛(长春)-重现赛

提交代码