You have a warehouse with containers filled with an infinite number of candies. The containers are arranged in a single row, equally spaced to be meter apart. You also have robots that can pick up piece of candy and transport it between any two containers.
The robots take instructions in the form of queries consisting of two integers, and , respectively. To execute a query, a robot travels to container , picks up candy, transports it to container , and then stops at until it receives another query.
Calculate the minimum total distance the robots must travel to execute queries in order.
Note: You choose which robot executes each query.
The first line contains a single integer, (the number of test cases); each of the test cases is described over lines.
The first line of a test case has two space-separated integers, (the number of containers) and (the number of queries).
The subsequent lines each contain two space-separated integers, and , respectively; each line describes the query.
On a new line for each test case, print an integer denoting the minimum total distance that the robots must travel to execute the queries in order.