Minimum Time to Collect All Coins Challenge

You are given a maze with r rows and c columns. Starting at position (0, 0), your goal is to collect k coins placed at various positions in the maze and return to the starting point. The time taken to move from one point to another is the Manhattan distance, defined as \( |x_1 - x_2| + |y_1 - y_2| \).

Your task is to determine the minimum total time required to collect all coins and come back to the starting point.

inputFormat

The first line contains an integer T, the number of test cases. For each test case:

The first line contains three integers: r c k, where r and c denote the dimensions of the maze, and k is the number of coins.

If k > 0, then the next k lines each contain two integers indicating the coordinates (row, column) of a coin.

outputFormat

For each test case, output a single line with one integer representing the minimum time required to collect all coins and return to the starting point.## sample

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

8
4
0