#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 23) + 5;
const int M = 50;
const int P = 998244353;
char s[M][M];
vector<int> bel[M];
int n, limit, cnt, f[N], g[N], st[M], a[M][M], b[M][M], fa[M];
int fd(int x) { return (x == fa[x]) ? x : fa[x] = fd(fa[x]); }
void inc(int &x, int y) { ((x += y) >= P) && (x -= P); }
void dec(int &x, int y) { ((x -= y) < 0) && (x += P); }
void merge(int x, int y) {
  int u = fd(x), v = fd(y);
  fa[u] = v;
}
signed main() {
  cin >> n;
  for (int i = (0); i < (n); ++i) fa[i] = i;
  for (int i = (0); i < (n); ++i) scanf("%s", s[i]);
  for (int i = (0); i < (n); ++i)
    for (int j = (0); j < (n); ++j) {
      if (s[i][j] == 'X') a[i][j] = 1;
      if (s[i][j] == 'A') merge(i, j);
    }
  for (int i = (0); i < (n); ++i)
    for (int j = (0); j < (n); ++j) {
      if (s[i][j] != 'X') continue;
      if (fd(i) == fd(j)) {
        puts("-1");
        exit(0);
      }
    }
  for (int i = (0); i < (n); ++i) bel[fd(i)].push_back(i);
  for (int i = (0); i < (n); ++i)
    if (bel[i].size() > 1) st[cnt++] = i;
  for (int i = (0); i < (cnt); ++i)
    for (int j = (0); j < (cnt); ++j) {
      for (int u : bel[st[i]])
        for (int v : bel[st[j]])
          if (a[u][v]) b[i][j] = b[j][i] = 1;
    }
  limit = (1 << cnt), f[0] = 1;
  for (int i = (1); i < (limit); ++i)
    for (int j = (0); j < (cnt); ++j)
      if ((i >> j) & 1) {
        int S = (i ^ (1 << j));
        f[i] = f[S];
        for (int k = (0); k < (cnt); ++k)
          if (((S >> k) & 1) && b[j][k]) f[i] = 0;
        break;
      }
  for (int k = 1; k < limit; k <<= 1)
    for (int i = 0; i < limit; i += (k << 1))
      for (int j = i; j < i + k; ++j) {
        int nx = f[j], ny = f[j + k];
        f[j] = nx + ny, f[j + k] = nx - ny;
      }
  for (int i = (0); i < (limit); ++i) g[i] = 1, f[i] = (f[i] + P) % P;
  for (int k = (0); k < (n); ++k) {
    int sum = 0;
    for (int i = (0); i < (limit); ++i)
      ((__builtin_popcount(i)) & 1) ? inc(sum, g[i]) : dec(sum, g[i]);
    for (int i = (0); i < (limit); ++i) g[i] = 1ll * g[i] * f[i] % P;
    if (sum) {
      cout << (n - 1) + k << endl;
      exit(0);
    }
  }
  return 0;
}
