In the game of chess in 8×8 grid a knight can move in an interesting way. Its moves are like “L” shape. Aknightcanmovefromcell(r1,c1)tocell(r2,c2)ifandonlyif(r1−r2)2+(c1−c2)2 =5. For this problem consider a grid of size N × 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 withtwointegersN(4≤N≤1000)andK(1≤K≤16). EachofthenextKlinescontainstwo 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 1 83 23 45 67 Sample Output Case 1: 12