#include <cstdio>
#include <cstring>
#include <queue>

using std::priority_queue;

const int N = 30;

char grid[N][N + 1];
bool used[N][N][N][N];

struct Pos {
  int xa;
  int ya;
  int xi;
  int yi;
  Pos *p;

  Pos(int xa = 0, int ya = 0, int xi = 0, int yi = 0, Pos *p = 0)
    : xa(xa), ya(ya), xi(xi), yi(yi), p(p) {}

  bool operator==(const Pos &that) const {
    return this->xa == that.xa && this->ya == that.ya &&
           this->xi == that.xi && this->yi == that.yi;
  }

  int dist() const {
    int dx = xa - xi;
    int dy = ya - yi;
    return dx * dx + dy * dy;
  }

  bool operator<(const Pos &that) const {
    return this->dist() < that.dist();
  }
} close[N][N][N][N];

int main() {
  int n;
  for (;;) {
    scanf("%d", &n);
    if (n == 0) break;
    Pos src, dst;
    for (int i = 0; i < n; i++) {
      scanf("%s\n", grid[i]);
      for (int j = 0; j < n; j++) {
        char c = grid[i][j];
        switch (c) {
          case 'H':
            src.xa = i;
            src.ya = j;
            break;
          case 'S':
            dst.xa = i;
            dst.ya = j;
            break;
          case 'h':
            src.xi = i;
            src.yi = j;
            break;
          case 's':
            dst.xi = i;
            dst.yi = j;
            break;
        }
      }
    }
    memset(used, 0, sizeof(used));
    priority_queue<Pos> pq;
    pq.push(src);
    while (!pq.empty()) {
      
    }
  }
  return 0;
}