/* Solution to Plugged In by Bob Roos */

import java.io.*;
import java.util.*;
import java.text.*;

public class BF {
  public static int scenario; 
  public static int N, M; /* N = side length of mesh; M = number of pairs
*/
  public static int pair[][] = new int[10000][2];
  public static BufferedReader in;
  
  
  public static void getdata() throws Exception {
    int i;
    StringTokenizer tok;
  
    M = Integer.parseInt(in.readLine().trim());
    for (i = 0; i < M; i++) {
      tok = new StringTokenizer(in.readLine().trim());
      pair[i][0] = Integer.parseInt(tok.nextToken().trim());
      pair[i][1] = Integer.parseInt(tok.nextToken().trim());
    }
  }
  
  
  public static int dist(int r1, int c1, int r2, int c2) {
     return 1 + (int)(Math.abs(r2-r1) + Math.abs(c2-c1));
  }
  
  
  public static void processdata() {
    int i,j,k,l,m;
    int row1,col1,row2,col2,temprow,tempcol;
    double average,minavg;
    NumberFormat fmt;
  
    minavg = 1e38;
  
    /* for each rotation ... */
    for (i = 0; i < 3; i++) {
 
      /* for each horizontal reflection ... */
      for (j = 0; j <= 1; j++) {
 
        /* for each vertical reflection ... */
        for (k = 0; k <= 1; k++) {
 
          /* for each pair ... */
          average = 0.0;
          for (l = 0; l < M; l++) {
            row1 = (pair[l][0]-1)/N;
            row2 = (pair[l][1]-1)/N;
            col1 = (pair[l][0]-1)%N;
            col2 = (pair[l][1]-1)%N;
            for (m = 0; m < i; m++) {
              temprow = col2;
              tempcol = N - row2 - 1;
              row2 = temprow;
              col2 = tempcol;
            }
            if (j > 0)
              col2 = N - col2 - 1;
            if (k > 0)
              row2 = N - row2 - 1;
 /*
  printf("debug: %d -> (%d,%d), %d->(%d,%d)\n",pair[l][0],row1,col1,
                                              pair[l][1],row2,col2);
 printf("       dist = %d\n",dist(row1,col1,row2,col2));
 */
            average += dist(row1,col1,row2,col2);
          }
          if (average/M < minavg) minavg = average/M;
        }
      }
    }
    fmt = NumberFormat.getNumberInstance();
    fmt.setMaximumFractionDigits(4);
    fmt.setMinimumFractionDigits(4);
    System.out.println("Scenario " + scenario + ": smallest average = "
      + fmt.format(minavg));
  }
  
  public static void main(String[] args) throws Exception {
    in = new BufferedReader(new InputStreamReader(System.in));
    scenario = 0;
    boolean first = true;
    
    while (true) {
      N = Integer.parseInt(in.readLine().trim());
      if (N <= 0) 
        break;
      if (!first)
        System.out.println();
      first = false;
      scenario++;
      getdata();
      processdata();
    }
  }
}