Time Limit: 1 s
Memory Limit: 128 MB

Submission：21
AC：8
Score：99.54

Bob and Alice have been living in HZNU for two years, every noon they will meet in a certain place on campus to see each other. Bob always starts from Shu Yuan yet Alice always starts from Bowen Yuan. Bob found that several places where they meet are always fixed, and he wants to know the total number of the places.

The question can be simplified to there are N (1<=N<=1000) Bowen Yuan buildings. From north to south, the number is 1 to N, there has M (1<=M<=1000) Shu Yuan buildings. From south to north, the number is 1 to M. Mark K (1<=K<=N*M) the total number of the roads connecting the Bowen Yuan and Shu Yuan between them(you can think road as a line). Each of the roads connect Bowen Yuan in one side, and the Shu Yuan other side. Every time Bob starts from Xth Shu Yuan building, and Alice will know the location he starts, and choose a way to Yth Shu Yuan building, and two load should Meets the following conditions:

- 1.X != Y.
- 2.There is an intersection of two roads except the point of Shu Yuan buildings and Bowen Yuan buildings.

- 3.X mod L is equal to Y mod L (1<=L<=100),a mod b denotes the remainder of a modulo b.

they will meet at point of intersection. So how many places they usually meet? (We Make sure there is no three and above road can meet at one point).

The first line is an integer T which is the number of test cases.

For each test case, the first line is an integer N (1<=N<=1000),M (1<=M<=1000),K (1<=N<=N*M),L (1<=L<=100). In following K lines, each line contains two integers a[i] and b[i], where a[i] is the ID of Bowen Yuan buildings, and b[i] is the ID of Shu Yuan buildings. (1<=a[i]<=N,1<=b[i]<=M)

For each test case, you should print first the identifier of the test case and then the number of places Bob and Alice meet.

input

3
3 4 4 1
1 1
2 2
3 3
3 4
3 4 4 2
1 1
2 2
3 3
3 4
4 3 4 1
1 1
2 2
3 3
4 3

output

Case 1: 5
Case 2: 2
Case 3: 5