Tanya likes to play Bomberman. In this game there is an arena which is a two dimensional grid of cells. In each cell there may be some monsters or none, and there are total P monsters in the arena. BomberMan plants a bomb at any cell, and chooses to demolish all the monsters of that row or that column.

For planting each bomb, BomberMan has to spend some K amount of energy. As Tanya is smart, she wants to minimize the number of bombs to be planted to destroy all the monsters, so that BomberMan has to spend least amount of energy. Determine the total amount of energy BomberMan has to spend, if Tanya plays the game optimally.

Input:

The first line contains number of test cases, t test cases follow.

The first line of each test case contains 2 integers K and P, the amount of energy BomberMan spends to plant one bomb, and the number of monsters in the arena, respectively .

P lines follow. Each of the p lines has 2 integers X and Y denoting the cell in which the monster is present.

Output:

Print the Amount of energy BomberMan has to spend to destroy all the monsters.

Constraints:

    1 <= t <= 10
    1 <= K <= 10^5
    1 <= P <= 10^5
    1 <= X, Y <= 10^9