B. Beingawesomeism

• Quiz
  • https://codeforces.com/contest/1281/problem/D
• AC
  • https://codeforces.com/contest/1280/submission/92201582
• 解説
  • editorialの通り、ひたすら場合分け。考察難易度は低い
• 学び
  • より小さい答えになるものをコードの前方に書く
  • 長くなりがちだし、提出後にWAになりやすく、はまりやすい。コンテスト中ははまる危険度が高い

bool is_A_line(string& s){
  for(char c : s){
    if(c!='A') return false;
  }
  return true;
}

// for codeforces
void solve(){
  // input
  ll R,C;cin>>R>>C;
  VS S(R);
  rep(i,R)cin>>S[i];

  // impossible easy case
  {
    ll p_cnt=0;
    for(string s : S){
      for(char c : s){
        if(c=='P') p_cnt++;
      }
    }
    if(p_cnt==R*C){
      p("MORTAL"); return;
    }
    ll a_cnt = R*C - p_cnt;
    if(a_cnt==R*C){
      p(0); return; // 忘れがち
    }
  }

  // P-exist range
  ll min_x = inf;
  ll min_y = inf;
  ll max_x = -1;
  ll max_y = -1;
  rep(i,R){
    rep(j,C){
      char c = S[i][j];
      if(c=='P'){
        chmin(min_y,i);
        chmax(max_y,i);
        chmin(min_x,j);
        chmax(max_x,j);
      }
    }
  }

  // about x
  rep(i,R){
    string s = S[i];
    ll len = max_x - min_x + 1;
    string sub = s.substr(min_x, len);
    if(min_y<=i && i<=max_y) continue; // 間だとダメ
    if(is_A_line(sub)){
      p(1); return;
    }
  }
  // about y
  rep(x,C){
    stringstream ss;
    rep(i,R) ss<<S[i][x];
    string s = ss.str();
    ll len = max_y - min_y + 1;
    string sub = s.substr(min_y, len);
    if(min_x<=x && x<=max_x) continue; // 間だとダメ
    if(is_A_line(sub)){
      p(1); return;
    }
  }

  // 一撃で終わらなかった場合のコーナー
  {
    string s = S[0];
    if(s[0]=='A' or s.back()=='A'){
      p(2); return;
    }
    s = S[R-1];
    if(s[0]=='A' or s.back()=='A'){
      p(2); return;
    }
  }

  // 以降、コーナーは全てP
  // P-exist rangeをつつみこむAラインがあれば2回で済む
  // about x
  rep(i,R){
    string s = S[i];
    ll len = max_x - min_x + 1;
    string sub = s.substr(min_x, len);
    if(is_A_line(sub)){
      p(2); return;
    }
  }
  // about y
  rep(x,C){
    stringstream ss;
    rep(i,R) ss<<S[i][x];
    string s = ss.str();
    ll len = max_y - min_y + 1;
    string sub = s.substr(min_y, len);
    if(is_A_line(sub)){
      p(2); return;
    }
  }

  // はじっこにAがあるなら3回で可能
  if(S[0].find("A")!=string::npos){
    p(3); return;
  }
  if(S[R-1].find("A")!=string::npos){
    p(3); return;
  }
  rep(i,R){
    if(S[i][0]=='A'){
      p(3);return;
    }
    if(S[i][C-1]=='A'){
      p(3);return;
    }
  }

  p(4);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}