Time Limit: 3000 MS    Memory Limit: 65536 K 


Description

Your job is to calculate (S1 XOR S2 XOR XOR Sn) mod 1000000007, where Li <= Si <= Hi, 1 <= i <= n.

Input

The first line of the input is an integer T (T <= 100), which stands for the number of test cases you need to solve. Every test case begins with an integer n (1 <= n <= 100), and followed by n pairs of integers L1, H1, L2, H2, ,Ln, Hn (1<=Li<=Hi<=10^9, 1<=i<=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.

Sample Input

2 1 1 10 2 1 2 2 3

Sample Output

Case #1: 55 Case #2: 6

Hint

A bitwise XOR performs the logical 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) XOR 0011(decimal 3) = 0110(decimal 6).

Source

The 9th UESTC Programming Contest Final