Alice has a chess board with n rows and m columns. There are k obstacles on the board placed exactly in cells. Two different rooks form a bad pair if they stay in one row or in one column and there are no obstacles between them.

Alice want to know a maximal number of rooks which she can put on the board without bad pairs. Help her calculate this number.

You have to solve this problem for several test cases.

$INPUT$

The first line of the input contains a single integer $tests$ - a number of test cases.

Each test case is given in the following format:

The first line contains a three integers n, m and k ($1 \leq n, m \leq 500$, $0 \leq k < n \cdot m$) - a number of rows, a number of columns and a number of obstacles.

Then follow k lines with obstacles description. The i-th of these lines contains two integers $r_i$ and $c_i$ ($1 \leq r_i \leq n$, $1 \leq c_i \leq m$) - a row number of i-th obstacle and a column number of i-th obstacle.

Guaranteed that all obstacles are placed in the different cells.

Guaranteed that $\sum_{i=1}^{tests} n_i \cdot m_i \leq 250000$.

$OUTPUT$

For each test case print a single integer number - an answer of the problem.