Array Reversion

Time limit: 15 seconds

Problem

Here is an array A of size n. Initially A[i] = i for all i between 0 and n - 1 inclusively. m reverse operations are applied to the array. A reverse operation is defined by two integers (x, y). It specifies that the sub-array starting at index x and ending at index y needs to be reversed.

For example, suppose n is 10 and there are two reverse operations, (1, 5) and (3, 7).

Initially, the content of A is:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

After the reverse operation (1, 5), the content of A is:
0, 5, 4, 3, 2, 1, 6, 7, 8, 9

After the reverse operation (3, 7), the content of A is:
0, 5, 4, 7, 6, 1, 2, 3, 8, 9

In this problem, your task is to simulate the reverse operations in the array. Instead of printing out the whole array, you are required to evaluate the following formula to show that the resulting array is correct:

Input

The input starts with the number of test cases t, where t is at most 200. t test cases follow. For each case, the first line contains n and m, where n is at most 1000000 and m is at most 1000. Each of the next m lines gives two integers xk and yk, which defines one reverse operation.

Output

For each test case, evaluate the formula after applying the reverse operations and print the result.

Sample Input

2
10 2
1 5
3 7
10 2
1 5
3 7

Sample output

547612389
547612389

Author

Louis Siu