input:

2 1
3 1 2
10 10
2 3 6
2 10 2
4
3 4 2
2 10 8
1 5 7
3 6 9
3 2 4
4
1 2 3
100 1000
2 12 76
1 6 97
3 80 78
3 23 75
3 88 78
3 48 11
4
4
2 22 89
4
2 60 11
1 92 11
2 39 49
4
4
1 22 47
1 48 14
1 60 58
1 37 40
3 4 36
4
2 39 55
1 62 71
4
1 91 4
4
1 50 49
3 42 29
2 73 47
1 28 93
2 22 97
2 50 32
1 17 38
4
2 8 22...

output:

Case 1: 2
Case 2: 26
Case 3: 2622
Case 4: 10213
Case 5: 2983
Case 6: 2499756727
Case 7: 252019
Case 8: 25055565
Case 9: 2500000000
Case 10: 2500000000

result:

ok 10 lines