uva12546測資B

Input: 
15
2
5 1
3 1
2
5 2
3 1
1
11 1
1
11 4
2
2 3
5 3
2
2 4
5 4
3
7 2
2 2
3 2
3
2 3
5 3
7 3
3
2 4
3 4
11 4
4
2 3
3 3
5 2
7 2
4
2 3
3 3
5 4
7 4
5
2 2
3 2
5 2
7 3
11 3
5
2 4
3 3
5 2
7 3
11 4
5
2 3
3 4
5 4
7 4
11 4
5
11 4
3 4
5 4
7 4
2 3
Output: 
Case 1: 92
Case 2: 642
Case 3: 34
Case 4: 89310
Case 5: 21709
Case 6: 321695
Case 7: 73839
Case 8: 29936161
Case 9: 175606690
Case 10: 59511645
Case 11: 391232451
Case 12: 124543887
Case 13: 935045674
Case 14: 942600170
Case 15: 942600170