#include <bits/stdc++.h>
using namespace std;
template <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T gcd(T a, T b) {
  return a ? gcd(b % a, a) : b;
}
template <class T>
int sgn(T x) {
  return x > 0 ? 1 : (x < 0 ? -1 : 0);
}
const long double pi = 2 * asinl((long double)1.0);
const int M = 1 << 16;
const int M16 = M - 1;
int popcnt[M];
int precalc() {
  for (int i = 0; i < M; i++) {
    popcnt[i] = __builtin_popcount(i);
  }
  return 0;
}
int pre = precalc();
int popcount(int x) { return popcnt[x & M16] + popcnt[x >> 16]; }
const int N = 100;
int n;
int m;
int ct;
vector<int> comp[N];
int id_comp[N];
vector<int> v[N];
vector<int> b;
string s[N];
void dfs(int x) {
  if (id_comp[x] != -1) return;
  id_comp[x] = ct;
  comp[ct].push_back(x);
  for (auto y : v[x]) dfs(y);
}
vector<int> mis;
int mx_mis;
int M1;
void calc(int mask, int h, int independent_set) {
  if (mask == 0) {
    if (h > mx_mis) {
      mis.clear();
      mx_mis = h;
      mis.push_back(independent_set);
    } else if (h == mx_mis) {
      mis.push_back(independent_set);
    }
    return;
  }
  int res = ct, pos = ct, cur_mask = mask;
  while (cur_mask) {
    int i = __builtin_ctz(cur_mask);
    cur_mask -= 1 << i;
    int cur = popcount(b[i] & mask);
    if (cur < res) {
      res = cur;
      pos = i;
    }
  }
  cur_mask = b[pos] & mask;
  while (cur_mask) {
    int i = __builtin_ctz(cur_mask);
    cur_mask -= 1 << i;
    calc(mask & (b[i] ^ M1), h + 1, independent_set | (1 << i));
  }
}
int main() {
  scanf("%d ", &n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (s[i][j] == 'A') {
        v[i].push_back(j);
      }
    }
  }
  memset(id_comp, -1, sizeof(id_comp));
  for (int i = 0; i < n; i++) {
    if (id_comp[i] == -1) {
      dfs(i);
      if (((int)comp[ct].size()) > 1)
        ct++;
      else {
        id_comp[comp[ct].front()] = -i - 1;
        comp[ct].clear();
      }
    }
  }
  M1 = (1 << ct) - 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (s[i][j] == 'X') {
        if (id_comp[i] == id_comp[j]) {
          puts("-1");
          return 0;
        }
      }
    }
  }
  b.resize(ct);
  for (int i = 0; i < ct; i++) {
    for (int j = 0; j < ct; j++) {
      if (i == j) {
        b[i] |= 1 << j;
        continue;
      }
      bool ok = true;
      for (auto x : comp[i]) {
        for (auto y : comp[j]) {
          if (s[x][y] == 'X') {
            ok = false;
            break;
          }
        }
      }
      b[i] |= (!ok) << j;
    }
  }
  vector<int> dp(1 << ct);
  mis.reserve(1 << ct);
  for (int mask = 1; mask < (1 << ct); mask++) {
    mis.clear();
    mx_mis = 0;
    calc(mask, 0, 0);
    dp[mask] = ct;
    for (auto submask : mis) {
      dp[mask] = min(dp[mask & ~submask] + 1, dp[mask]);
    }
  }
  cout << (n - 1) + dp[M1] << endl;
  cerr << clock() << endl;
  return 0;
}
