#include<cstdio>

int n,i[1000][1000];

int main()

{

scanf("%d",&n);

for (int a=1;a<=n;a++)

for (int b=1;b<=n;b++)

scanf("%d",&i[a][b]);

for (int a=1;a<=n;a++)

  for (int b=1;b<=n;b++)

    for (int c=1;c<=n;c++)

       if (i[b][c]<i[b][a]+i[a][c])

         i[b][c]=i[b][c];

       else

         i[b][c]=i[b][a]+i[a][c];

scanf("%d",&n);

for (int a=1;a<=n;a++)

{

int x,y;

scanf("%d%d",&x,&y);

printf("%d\n",i[x][y]);

}

return 0;

}