#include <stdio.h>
#include <stdlib.h>

int path[100][100];
int way[10000];

int cmp(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

int main()
{
	int t, i, j, k, n, m, p;
	
//	freopen("in.dat", "r", stdin);
	scanf("%d", &t);

	for (n = 0; n < t;)
	{
		 scanf("%d%d", &p, &m);

		 for (i = 0; i < m; i++)
		 {
			 for (j = 0; j < m; j++)
			 {
				 scanf("%d", &path[i][j]);
				 if (path[i][j] == -1 || i == j)
				 {
					 path[i][j] = 1000000;
				 }
			 }
		 }

		 for (k = 0; k < m; k++)
		 {
			 for (i = 0; i < m; i++)
			 {
				 for (j = 0; j < m; j++)
				 {
					 if (i == j)
					 {
						 continue;
					 }
					 if (path[i][k] + path[k][j] < path[i][j])
					 {
						 path[i][j] = path[i][k] + path[k][j];
					 }
				 }
			 }
		 }
		 for (i = 0; i < m; i++)
		 {
			 for (j = 0; j < m; j++)
			 {
//				 printf("%d\t", path[i][j]);
				 way[i * m + j] = path[i][j];
			 }
//			 printf("\n");
		 }
		 
		 qsort(way, m * m, sizeof(way[0]), cmp);
		 
		 for (i = 0; i < m * m; i++)
		 {
//			 printf("%d\n", way[i]);
		 }
		 
		 if (p * m * (m - 1) % 100 == 0)
		 {
			 k = p * m * (m - 1) / 100;
		 }
		 else
		{
			k = (p * m * (m - 1)) / 100 + 1;
		}
		n++;
		 printf("Scenario #%d:\n%d\n\n", n, way[k - 1]);
	}
	
	return 0;
}