SOLVE
LATER
Consider the following game. There is a field with n rows and 3 columns. Some cells contain obstacles. But the first row is always empty. Let's define cell in i-th row and j-th column as \((i, j)\). From cell \((i, j)\) you can go to cells \((i + 1, j - 1)\), \((i + 1, j)\) and \((i + 1, j + 1)\) if such cell exists (you can't go out of field) and doesn't contain obstacle. You can start in any column in the first row. What is the maximum i, such that i-th row is reachable?
Input format
Given several test cases.
First line of input contains integer T (\(1 \leq T \leq 3 \cdot 10^5\)) — number of test cases.
Then follow T blocks of input.
The first line of block contains integers n and q (\(2 \leq n \leq 10^9\), \(0 \leq q \leq \min(3 \cdot 10^5, 3 \cdot (n - 1))\)) — number of rows and number of obstacles, respectively.
Then follow q lines with obstacles description.
The i-th of them contains integers x and y (\(2 \leq x \leq n\), \(1 \leq y \leq 3\)) — the coordinates of i-th obstacle, located at \((x, y)\).
Coordinates of all obstacles in a single test case are pairwise distinct.
Sum of all q in input doesn't exceed \(3 \cdot 10^5\).
Output format
For each block print single integer — the maximum row that is possible to be reached.
In the first test case one of the optimal paths is \((1, 2)\), \((2, 1)\), \((3, 2)\), \((4, 2)\). So the row 4 is possible to be reached.
In the second test case there are no possible moves from \((1, 2)\). So only the row 1 is possible to be reached.