#include <bits/stdc++.h>
using namespace std;
const int N = 50;
mt19937 rng(20020415);
int n, fa[N], ans, id[N], tt, dp[1 << 19], p[N], col[N];
char G[N][N];
bool ban[N][N], key[N], can[1 << 19];
bitset<N> vis;
int getf(int x) { return x == fa[x] ? x : fa[x] = getf(fa[x]); }
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> G[i], fa[i] = i;
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
      if (G[i][j] == 'A') fa[getf(i)] = getf(j), key[i] = key[j] = 1;
  memset(id, -1, sizeof(id));
  for (int i = 0; i < n; i++)
    if (getf(i) == i && key[i]) id[i] = tt++;
  for (int i = 0; i < n; i++)
    if (getf(i) != i) id[i] = id[getf(i)];
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
      if (G[i][j] == 'X' && ~id[i] && ~id[j]) {
        if (id[i] == id[j]) return cout << -1, 0;
        ban[id[i]][id[j]] = ban[id[j]][id[i]] = 1;
      }
  if (!tt) return cout << n - 1, 0;
  if (tt <= 19) {
    for (int s = 0; s < (1 << tt); s++) {
      can[s] = 1;
      for (int i = 0; i < tt && can[s]; i++)
        if (s >> i & 1)
          for (int j = 0; j < tt && can[s]; j++)
            if ((s >> j & 1) && ban[i][j]) can[s] = 0;
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int s = 1; s < (1 << tt); s++)
      for (int t = s; t; t = (t - 1) & s)
        if (can[t]) dp[s] = min(dp[s], dp[s ^ t] + 1);
    cout << dp[(1 << tt) - 1] + n - 1;
  } else {
    for (int i = 0; i < tt; i++) p[i] = i;
    int ans = 1e9;
    for (int T = 1; T <= 10000; T++) {
      shuffle(p, p + tt, rng);
      int mx = 0;
      for (int i = 0; i < tt; i++) {
        vis.reset();
        for (int j = 0; j < i; j++)
          if (ban[p[i]][p[j]]) vis[col[j]] = 1;
        for (int j = 0;; j++)
          if (!vis[j]) {
            col[i] = j;
            break;
          }
        mx = max(mx, col[i]);
      }
      ans = min(ans, mx + 1);
    }
    cout << ans + n - 1;
  }
  return 0;
}
