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.