#include <stdio.h>
#include <math.h>

int scenario; 
int N, M; /* N = side length of mesh; M = number of pairs */
int pair[10000][2]; /* N <= 100, so at most 100*100 pairs */


void getdata()
{
  int i;

  scanf("%d", &M);
  for (i = 0; i < M; i++)
    scanf("%d %d", &pair[i][0], &pair[i][1]);
}


int dist(int r1, int c1, int r2, int c2)
{
   return 1 + (int)(fabs(r2-r1) + fabs(c2-c1));
}


void processdata()
{
   int i,j,k,l,m;
   int row1,col1,row2,col2,temprow,tempcol;
   double average,minavg;

   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;
       }
     }
   }
   if (scenario > 1) {
     printf("\n");
   }
   printf("Scenario %d: smallest average = %0.4lf\n", scenario, minavg);
}

int main()
{
  scenario = 0;
  while (scanf("%d",&N)  && N > 0)
  {
    scenario++;
    getdata();
    processdata();
  }
}