#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


/*
template <class T> struct Vector : vector<T> {
  using vector<T>::vector;
  void checkIndex(long long i) const {
    const long long sz = this->size();
    if (!(0 <= i && i < sz)) {
      cerr << "[Vector] Bad index " << i << " (size " << sz << ")" << endl;
      cerr << *this << endl;
      assert(false);
    }
  }
  T operator[](long long i) const {
    checkIndex(i);
    return this->at(i);
  }
  T &operator[](long long i) {
    checkIndex(i);
    return this->at(i);
  }
};
#define vector Vector
//*/


////////////////////////////////////////////////////////////////////////////////
// neighbors of u: [pt[u], pt[u + 1])
struct Graph {
  int n;
  vector<pair<int, int>> edges;
  vector<int> pt;
  vector<int> zu;

  Graph() : n(0), edges() {}
  explicit Graph(int n_) : n(n_), edges() {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    edges.emplace_back(u, v);
  }
  void build(bool directed) {
    const int edgesLen = edges.size();
    pt.assign(n + 1, 0);
    if (directed) {
      for (int i = 0; i < edgesLen; ++i) {
        ++pt[edges[i].first];
      }
      for (int u = 0; u < n; ++u) pt[u + 1] += pt[u];
      zu.resize(edgesLen);
      for (int i = edgesLen; --i >= 0; ) {
        zu[--pt[edges[i].first]] = edges[i].second;
      }
    } else {
      for (int i = 0; i < edgesLen; ++i) {
        ++pt[edges[i].first];
        ++pt[edges[i].second];
      }
      for (int u = 0; u < n; ++u) pt[u + 1] += pt[u];
      zu.resize(2 * edgesLen);
      for (int i = edgesLen; --i >= 0; ) {
        const int u = edges[i].first, v = edges[i].second;
        zu[--pt[u]] = v;
        zu[--pt[v]] = u;
      }
    }
  }

  inline int deg(int u) const {
    return pt[u + 1] - pt[u];
  }
  inline int operator[](int j) const {
    return zu[j];
  }
  friend ostream &operator<<(ostream &os, const Graph &g) {
    os << "Graph(n=" << g.n << ";";
    for (int u = 0; u < g.n; ++u) {
      os << " " << u << ":[";
      for (int j = g.pt[u]; j < g.pt[u + 1]; ++j) {
        if (j != g.pt[u]) os << ",";
        os << g[j];
      }
      os << "]";
    }
    os << ")";
    return os;
  }
};
////////////////////////////////////////////////////////////////////////////////

// gg: bipartite graph between {vertex} and {biconnected component}
//   (gg.n - n) biconnected components
// f: DFS forest
struct Biconnected {
  int n;
  Graph g, f, gg;

  Biconnected() : n(0), stackLen(0), zeit(0) {}
  explicit Biconnected(int n_) : n(n_), g(n_), stackLen(0), zeit(0) {}
  void ae(int u, int v) {
    g.ae(u, v);
  }

  int stackLen;
  vector<int> stack;
  vector<int> par, rs;
  int zeit;
  vector<int> dis, fin, low;
  void dfs(int u) {
    stack[stackLen++] = u;
    dis[u] = low[u] = zeit++;
    for (int j = g.pt[u]; j < g.pt[u + 1]; ++j) {
      const int v = g[j];
      if (~dis[v]) {
        if (low[u] > dis[v]) low[u] = dis[v];
      } else {
        f.ae(u, v);
        par[v] = u;
        rs[v] = rs[u];
        dfs(v);
        if (low[u] > low[v]) low[u] = low[v];
        if (dis[u] == low[v]) {
          const int x = gg.n++;
          for (; ; ) {
            const int w = stack[--stackLen];
            gg.ae(w, x);
            if (w == v) break;
          }
          gg.ae(u, x);
        }
      }
    }
    fin[u] = zeit;
  }
  void build() {
    g.build(false);
    f = Graph(n);
    gg = Graph(n);
    stack.resize(n);
    par.assign(n, -1);
    rs.assign(n, -1);
    zeit = 0;
    dis.assign(n, -1);
    fin.assign(n, -1);
    low.assign(n, -1);
    for (int u = 0; u < n; ++u) if (!~dis[u]) {
      stackLen = 0;
      rs[u] = u;
      dfs(u);
    }
    f.build(true);
    gg.build(false);
  }

  // Returns true iff u is an articulation point
  //   <=> # of connected components increases when u is removed.
  inline bool isArt(int u) const {
    return (gg.deg(u) >= 2);
  }

  // Returns w s.t. w is a child of u and a descendant of v in the DFS forest.
  // Returns -1 instead if v is not a proper descendant of u
  //   O(log(deg(u))) time
  int dive(int u, int v) const {
    if (dis[u] < dis[v] && dis[v] < fin[u]) {
      int j0 = f.pt[u], j1 = f.pt[u + 1];
      for (; j0 + 1 < j1; ) {
        const int j = (j0 + j1) / 2;
        ((dis[f[j]] <= dis[v]) ? j0 : j1) = j;
      }
      return f[j0];
    } else {
      return -1;
    }
  }
  // Returns true iff there exists a v-w path when u is removed.
  //   O(log(deg(u))) time
  bool isStillReachable(int u, int v, int w) const {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    assert(0 <= w); assert(w < n);
    assert(u != v);
    assert(u != w);
    if (rs[v] != rs[w]) return false;
    if (rs[u] != rs[v]) return true;
    const int vv = dive(u, v);
    const int ww = dive(u, w);
    if (~vv) {
      if (~ww) {
        return (vv == ww || (dis[u] > low[vv] && dis[u] > low[ww]));
      } else {
        return (dis[u] > low[vv]);
      }
    } else {
      if (~ww) {
        return (dis[u] > low[ww]);
      } else {
        return true;
      }
    }
  }
};

////////////////////////////////////////////////////////////////////////////////


constexpr int DX[4] = {+1, 0, -1, 0};
constexpr int DY[4] = {0, +1, 0, -1};
constexpr int INF = 1001001001;
constexpr int MAX_V = 400'010;

char buf[MAX_V];

int M, N;
vector<string> A;

int V;
vector<vector<int>> ids;
int to[MAX_V][8];

Biconnected B;
vector<int> ex, dp, DP;
void dfs(int u) {
  for (int j = B.f.pt[u]; j < B.f.pt[u + 1]; ++j) {
    const int v = B.f[j];
    dfs(v);
    dp[u] |= dp[v];
  }
  if (u < V) dp[u] |= ex[u];
}
void DFS(int u) {
  const int len = B.f.pt[u + 1] - B.f.pt[u];
  vector<int> ls(len + 1, 0), rs(len + 1, 0);
  for (int k = 0; k < len; ++k) {
    const int v = B.f[B.f.pt[u] + k];
    ls[k + 1] = ls[k] | dp[v];
  }
  for (int k = len; --k >= 0; ) {
    const int v = B.f[B.f.pt[u] + k];
    rs[k] = dp[v] | rs[k + 1];
  }
  for (int k = 0; k < len; ++k) {
    const int v = B.f[B.f.pt[u] + k];
    DP[v] = ls[k] | rs[k + 1];
    if (~B.par[u]) DP[v] |= DP[u];
    if (u < V) DP[v] |= ex[u];
  }
  for (int k = 0; k < len; ++k) {
    const int v = B.f[B.f.pt[u] + k];
    DFS(v);
  }
}
int getEx(int u, int v) {
  if (B.rs[u] != B.rs[v]) {
    return dp[v] | DP[v];
  }
  const int vv = B.dive(u, v);
  return (~vv) ? dp[vv] : DP[u];
}

bool vis[MAX_V][8];
int dist[MAX_V][8];

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d%d", &M, &N);
    A.resize(M);
    for (int x = 0; x < M; ++x) {
      scanf("%s", buf);
      A[x] = buf;
    }
    
    V = 0;
    vector<vector<int>> ids(M, vector<int>(N, -1));
    for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) if (A[x][y] != '#') {
      ids[x][y] = V++;
    }
// cerr<<"V = "<<V<<endl;
// cerr<<"ids = "<<endl;for(int x=0;x<M;++x){for(int y=0;y<N;++y){fprintf(stderr,"%2d ",ids[x][y]);}cerr<<endl;}
    for (int u = 0; u < V; ++u) {
      fill(to[u], to[u] + 8, -1);
    }
    ex.assign(V, 0);
    for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
      const int u = ids[x][y];
      if (~u) {
        for (int dir = 0; dir < 4; ++dir) {
          const int xx = x + DX[dir];
          const int yy = y + DY[dir];
          if (0 <= xx && xx < M && 0 <= yy && yy < N) {
            to[u][dir] = ids[xx][yy];
          } else {
            ex[u] |= 1 << dir;
          }
        }
      }
    }
    
    Biconnected b(V);
    for (int u = 0; u < V; ++u) for (int dir = 0; dir < 4; ++dir) {
      const int v = to[u][dir];
      if (~v && u < v) {
        b.ae(u, v);
      }
    }
    b.build();
// cerr<<"b.gg = "<<b.gg<<endl;
    B = Biconnected(b.gg.n);
    for (const auto &edge : b.gg.edges) {
      B.ae(edge.first, edge.second);
    }
    B.build();
// cerr<<"B.f = "<<B.f<<endl;
    dp.assign(B.n, 0);
    DP.assign(B.n, 0);
    for (int u = 0; u < B.n; ++u) if (!~B.par[u]) dfs(u);
    for (int u = 0; u < B.n; ++u) if (!~B.par[u]) DFS(u);
// cerr<<"dp = "<<dp<<endl;
// cerr<<"DP = "<<DP<<endl;
    
    int ents[4];
    {
      const int x = (M - 1) / 2;
      const int y = (N - 1) / 2;
      ents[0] = ids[M - 1][y];
      ents[1] = ids[x][N - 1];
      ents[2] = ids[0][y];
      ents[3] = ids[x][0];
    }
    for (int u = 0; u < V; ++u) for (int h = 4; h < 8; ++h) if (u != ents[h ^ 4]) {
      to[u][h] = ents[h ^ 4];
    }
    
    deque<int> que;
    for (int u = 0; u < V; ++u) {
      fill(vis[u], vis[u] + 8, false);
      fill(dist[u], dist[u] + 8, INF);
    }
    {
      int u = -1, me = -1;
      for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
        if (A[x][y] == 'b') u = ids[x][y];
        if (A[x][y] == 'p') me = ids[x][y];
      }
      // move, exit
      const int res = getEx(u, me);
      for (int h = 0; h < 8; ++h) if (~to[u][h]) {
        if (b.isStillReachable(u, me, to[u][h]) || (res >> h & 1)) {
          dist[u][h] = 0;
          que.push_back(u << 3 | h);
        }
      }
    }
    for (; !que.empty(); ) {
      const int u = que.front() >> 3;
      const int h = que.front() & 7;
      que.pop_front();
      if (!vis[u][h]) {
        vis[u][h] = true;
        const int c = dist[u][h];
// cerr<<c<<": "<<u<<" "<<h<<endl;
        auto update = [&](int dc, int v, int hh) -> void {
          if (chmin(dist[v][hh], c + dc)) {
            if (dc) {
              que.push_back(v << 3 | hh);
            } else {
              que.push_front(v << 3 | hh);
            }
          }
        };
        // move
        for (int hh = 0; hh < 8; ++hh) if (!vis[u][hh] && ~to[u][hh]) {
          if (b.isStillReachable(u, to[u][h], to[u][hh])) {
            update(0, u, hh);
          }
        }
        if (h < 4) {
          if (~to[u][h ^ 2]) {
            // push
            update(1, to[u][h ^ 2], h);
          } else if (!(ex[u] >> (h ^ 2) & 1) && ~to[u][h ^ 4]) {
            // enter
            update(0, u, h ^ 4);
          }
        }
        // exit
        const int res = getEx(u, to[u][h]);
        for (int hh = 0; hh < 4; ++hh) if ((res >> hh & 1) && ~to[u][hh]) {
          update(0, u, hh);
        }
      }
    }
    int ans = INF;
    {
      int u = -1, me = -1;
      for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
        if (A[x][y] == '-') u = ids[x][y];
        if (A[x][y] == '=') me = ids[x][y];
      }
      for (int h = 0; h < 8; ++h) if (~to[u][h]) {
        // move
        if (b.isStillReachable(u, to[u][h], me)) {
          chmin(ans, dist[u][h]);
        }
      }
    }
    printf("%d\n", (ans >= INF) ? -1 : ans);
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}