1027: SYH’s Easy Statistic Problem

Memory Limit：256 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：133 Solved：15

Description

SYH thinks this problem is the easiest problem in this contest. Help him to statistic how many numbers in the range of [Li, Ri] that module pi is mi.

Input

The first line conatins an integer T, means the number of test cases. For each test case, the first line contains four integers Li, Ri, pi and mi.
  

Output

For each test case ouput “Case: #x: y” in a single line. x is the test case number (starting from 1), and y is your answer.

Sample Input Copy 

2

1 7 4 0

2 11 3 1

Sample Output Copy 

Case #1: 1
Case #2: 3

HINT

For the first sample, only 4 satisfies.

For the second sample, 4, 7 and 10 all satisfy.



1 ≤ T ≤ 105, 1 ≤ Li, Ri, pi ≤ 109, 0 ≤ mi < pi.