High School Programming League Problems Archive

From Ramsey theorem we know that for every k, l pair there exists an integer: R(k, l) for that if n >= R(k, l), then if you color the edges of a complete graph on n vertices with red and blue then it contains a complete subgraph on k vertices whose edges are blue or a complete subgraph on l vertices whose edges are red. To get an impression of the theorem you have to count the number of complete subgraphs having k nodes with blue edges - K(k) and the number of complete subgraphs having l nodes with red edges - K(l) for each edge coloring.

To make the problem somewhat easier (or harder?) for each test the probability that an edge is red (or blue) is close to 1/2. This means that on n vertices you will see about n(n-1)/4 red edges.

Input

The first line contains the number of test cases T, where T <= 100. After it there is a blank line and also after every test. Each test starts with four integers n, k, l, e in this order, where 3 <= k <= l <= n < 100, here e is the number of red edges (we are not interested in very large monochromatic complete subgraphs, so you can assume that k, l <= 10 is also true). Then follow e lines, each of them gives two integers: x, y, it means that there is a red edge between points 0 <= x, y < n. All other edges are blue.

Output

For each test print the case number then the count of blue K(k) and red K(l) for the edge coloring.

Example

Input:
3

5 3 3 5
0 1
1 2
2 3
3 4
4 0

6 3 3 6
0 1
1 2
2 3
3 4
4 5
5 0

8 3 4 7
0 1
0 2
0 3
0 4
1 2
1 3
2 3


Output:
Case #1:
The number of blue K(3) is 0 and the number of red K(3) is 0.
Case #2:
The number of blue K(3) is 2 and the number of red K(3) is 0.
Case #3:
The number of blue K(3) is 25 and the number of red K(4) is 1.