Description

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

for case2: we can calculate like this: (1^2)+(1^3)+(2^2)+(2^3) = 6

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

Output

Case #1: 55
Case #2: 6

Hint

xor是按位异或. 一种位运算.