Problem H
Knight Tour
Input: Standard Input

Output: Standard Output

In the game of chess in 8 x 8 grid a knight can move in an interesting way. Its moves are like “L” shape. A knight can move from cell (r1, c1) to cell (r2, c2) if and only if (r1 - r2)² + (c1 - c2)² = 5.

For this problem consider a grid of size N x N.  There are K interesting cell in our grid. We have a knight which can start his journey from any cell it likes in the grid. His aim is to visit all interesting cells at least once and back to its initial position.

Your task is to calculate the minimum number of moves required for the knight to finish its journey.

Image: knight moves

Input

Input will start with an integer T(T≤100) which denotes the number of test cases. Each case starts with two integers N(4≤N≤1000) and K(1≤K≤16). Each of the next K lines contains two integers R(1≤R≤N) and C(1≤C≤N). Here (R, C) represents an interesting cell.  

Output

Output one line for each test case. Print the case number followed by the number of minimum moves required.

Look at the sample input output for exact format.

Sample Input                             Output for Sample Input