Many years have passed … *Bakkar* is now a computer science student and its his third year at college. This year they study an Algorithm course where they enjoy learning new algorithmic and problem solving techniques. The course instructor loves to give them programming puzzles to help him discover talented and hardworking students.
Moreover the instructor is a chess maniac; he loves to make programming puzzles about chess. Today the instructor told the students that he is going to make a quiz with a bonus value of 10 points (which is very high by the way). The students were very excited and motivated to know the problem and of course to be able to solve it to get the bonus ;).
The problem description is as follows:
*Unlike the normal 8 by 8 chessboard, this game is played on a N rows by M columns chessboard. You are allowed to place some Rooks on the chessboard. A rook placed on the cell (i,j) will attack all the cells in the ith row and jth column.*
*You really hate some cells on this chessboard, and you want to super-attack these cells by rooks. For a cell to be super-attacked, both of it's row and column must be attacked by rooks. A rook super-attacks the cell directly beneath it.*
*The goal of the game is to use the minimum number of rooks to super-attack all of the cells you hate. Since you thought that task is too easy, you also decided to count the number of different ways to solve this game with the minimum number of rooks. Rooks are identical, and two ways are considered different if a position has a rook in one way but is empty in the other. Since this number can be very large, you only need to calculate it mod 1,000,000,007.*
Interesting problem isn't it?!! Well *Bakkar* is very excited and already has a solution in his mind for the problem.
Ok; the time is over now for the quiz and *Bakkar* is claiming that he has solved the problem successfully and you as a Teaching Assistant in the course musr prepare a program to validate the students' solutions. Let's validate *Bakkar*'s solution by running some test cases against his solution and recording it for evaluation by the validator.
Your program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1 ≤ *T* ≤ 100). Followed by *T* test cases, each test case starts with a line containing three integers separated by a single space *N*, *M* and *K* (1 ≤ *N*,*M* ≤ 109 , 1 ≤ *K* ≤ 103), representing the number of rows and columns in the chess board, and the number of cells you hate, respectively. The next *K* lines represent the cells you hate. Each line contains two integers separated by a single space *r* and *c* (1 ≤ *r* ≤ *N* , 1 ≤ *c* ≤ *M*) which represent the represent the row and column of a cell you hate, respectively. All the cells will be distinct.
For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed 2 integers, space separated, representing the minimum number of rooks needed and the number of ways to place those rooks that *Bakkar*'s solution outputted.
## Input
Your program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1 ≤ *T* ≤ 100). Followed by *T* test cases, each test case starts with a line containing three integers separated by a single space *N*, *M* and *K* (1 ≤ *N*,*M* ≤ 109 , 1 ≤ *K* ≤ 103), representing the number of rows and columns in the chess board, and the number of cells you hate, respectively. The next *K* lines represent the cells you hate. Each line contains two integers separated by a single space *r* and *c* (1 ≤ *r* ≤ *N* , 1 ≤ *c* ≤ *M*) which represent the represent the row and column of a cell you hate, respectively. All the cells will be distinct.
## Output
For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed 2 integers, space separated, representing the minimum number of rooks needed and the number of ways to place those rooks that *Bakkar*'s solution outputted.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ N_k, M_k \in \mathbb{Z} $ denote the dimensions of the chessboard ($1 \leq N_k, M_k \leq 10^9$).
- Let $ K_k \in \mathbb{Z} $ denote the number of hated cells ($1 \leq K_k \leq 10^3$).
- Let $ H_k = \{(r_i, c_i) \mid i \in \{1, \dots, K_k\}\} $ be the set of hated cells, with all pairs distinct.
Let $ R \subseteq \{1, \dots, N_k\} $ be the set of rows containing at least one hated cell.
Let $ C \subseteq \{1, \dots, M_k\} $ be the set of columns containing at least one hated cell.
**Constraints**
1. $ 1 \leq T \leq 100 $
2. $ 1 \leq N_k, M_k \leq 10^9 $
3. $ 1 \leq K_k \leq 10^3 $
4. All hated cells in $ H_k $ are distinct.
**Objective**
For each test case $ k $, compute:
- The **minimum number of rooks** required to super-attack all hated cells:
$$
m_k = \max(|R|, |C|)
$$
- The **number of distinct ways** to place $ m_k $ rooks to achieve this, modulo $ 1,000,000,007 $:
$$
w_k = \sum_{i=\max(0, |R| + |C| - m_k)}^{\min(|R|, |C|)} \binom{|R|}{i} \binom{|C|}{i} i! \mod 1,000,000,007
$$
(Equivalently: if $ |R| = r $, $ |C| = c $, and $ m = \max(r, c) $, then $ w_k = \sum_{i = m - \min(r,c)}^{ \min(r,c) } \binom{r}{i} \binom{c}{i} i! \mod 10^9+7 $)
**Note**: The number of ways is the number of bijections between subsets of size $ \min(r,c) $ from $ R $ and $ C $, extended to $ m $ rooks by covering the excess rows or columns arbitrarily — equivalent to the number of partial bijections matching the required coverage.