Migrated from Lutece 372 Brute Xor

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Your job is to calculate $\sum(S_1\rm\ XOR\ S_2\rm\ XOR \cdots XOR\ S_n)\rm\ mod\ 1000000007$, where $L_i\leq S_i\leq H_i$, $1\leq i\leq n$.

Input

The first line of the input is an integer $T$ ($T\leq 100$), which stands for the number of test cases you need to solve.

Every test case begins with an integer $n$ ($1\leq n\leq 100$), and followed by n pairs of integers $L_1, H_1, L_2, H_2, \cdots ,L_n, H_n$ ($1\leq L_i\leq H_i\leq 10^9, 1\leq i\leq n$). Every pair occupies a line.

Output

For every test case, you should output Case #k: first, where $k$ indicates the case number and starts at $1$. Then output the answer. See sample for more details.

Samples

2
1
1 10
2
1 2
2 3

Case #1: 55
Case #2: 6

Note

A bitwise $\rm XOR$ performs the logical $\rm XOR$ operation on each pair of corresponding bits. The result in each position is $1$ if the two bits are different, and $0$ if they are the same. For example: 0101(decimal $5$)$\rm\ XOR$0011(decimal $3$) $=$ 0110(decimal $6$).

Resources

The 9th UESTC Programming Contest Final