uva12546測資A

Input: 
15
2
2 1
3 1
2
2 2
3 1
1
5 1
1
5 4
2
2 3
3 3
2
2 4
3 4
3
5 2
2 2
3 2
3
2 3
3 3
5 3
3
2 4
3 4
5 4
4
2 2
3 3
5 2
7 3
4
2 3
3 4
5 3
7 4
5
2 2
3 2
5 3
7 3
11 3
5
2 4
3 4
5 2
7 3
11 4
5
2 4
3 4
5 4
7 4
11 4
5
11 4
3 4
5 4
7 4
2 4
Output: 
Case 1: 41
Case 2: 117
Case 3: 16
Case 4: 3906
Case 5: 4935
Case 6: 43571
Case 7: 38565
Case 8: 2532789
Case 9: 139514275
Case 10: 211010535
Case 11: 512819727
Case 12: 510641506
Case 13: 700276702
Case 14: 534908330
Case 15: 534908330