#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 35;

int r[maxn][maxn][maxn], dp[maxn][maxn][maxn];

int biggest_stadium(int n, vector<vector<int>> f) {
    vector<vector<int>> pr_sum(n + 1, vector<int>(n + 1));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            f[i][j] ^= 1;
            pr_sum[i + 1][j + 1] = pr_sum[i + 1][j] + pr_sum[i][j + 1] - pr_sum[i][j] + f[i][j];
        }
    }
    if (pr_sum[n][n] == n * n - 1) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!f[i][j]) {
                    return n * n - min(i + 1, n - i) * min(j + 1, n - j);
                }
            }
        }
    }
    auto get = [&](int i1, int j1, int i2, int j2) {
        return pr_sum[i2][j2] - pr_sum[i1][j2] - pr_sum[i2][j1] + pr_sum[i1][j1];
    };
    vector<vector<int>> ll(n, vector<int>(n, -1)), rr(n, vector<int>(n, n)), dd(n, vector<int>(n, n));
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < n; ++j) {
            if (!f[i][j]) {
                ll[i][j] = j;
                dd[i][j] = i;
            } else {
                if (j > 0) {
                    ll[i][j] = ll[i][j - 1];
                }
                if (i + 1 < n) {
                    dd[i][j] = dd[i + 1][j];
                }
            }
        }
        for (int j = n - 1; j >= 0; --j) {
            if (!f[i][j]) {
                rr[i][j] = j;
            } else if (j + 1 < n) {
                rr[i][j] = rr[i][j + 1];
            }
        }
    }
    if (n <= 30) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int l = 0; l < n; ++l) {
                    r[i][j][l] = 0;
                    dp[i][j][l] = 0;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int l = 0; l < n; ++l) {
                for (int rv = l + 1; rv <= n; ++rv) {
                    if (get(i, l, i + 1, rv) == rv - l) {
                        if (dp[i][i][l] < rv - l) {
                            r[i][i][l] = rv;
                            dp[i][i][l] = rv - l;
                            ans = max(ans, dp[i][i][l]);
                        }
                    }
                }
            }
        }
        for (int width = 1; width < n; ++width) {
            for (int i = 0; i + width <= n; ++i) {
                for (int l = 0; l < n; ++l) {
                    int rv = r[i][i + width - 1][l];
                    if (dp[i][i + width - 1][l] == 0) {
                        continue;
                    }
                    for (int l2 = l; l2 < rv; ++l2) {
                        if (i > 0 && get(i - 1, l2, i, l2 + 1) == 1) {
                            int r2 = min(r[i][i + width - 1][l], rr[i - 1][l2]);
                            if (dp[i - 1][i + width - 1][l2] < dp[i][i + width - 1][l] + r2 - l2) {
                                r[i - 1][i + width - 1][l2] = r2;
                                dp[i - 1][i + width - 1][l2] = dp[i][i + width - 1][l] + r2 - l2;
                                ans = max(ans, dp[i - 1][i + width - 1][l2]);
                            }
                        }
                        if (i + width < n && get(i + width, l2, i + width + 1, l2 + 1)) {
                            int r2 = min(r[i][i + width - 1][l], rr[i + width][l2]);
                            if (dp[i][i + width][l2] < dp[i][i + width - 1][l] + r2 - l2) {
                                r[i][i + width][l2] = r2;
                                dp[i][i + width][l2] = dp[i][i + width - 1][l] + r2 - l2;
                                ans = max(ans, dp[i][i + width][l2]);
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
    bool check = true;
    for (int i1 = 0; i1 < n; ++i1) {
        for (int j1 = 0; j1 < n; ++j1) {
            for (int i2 = 0; i2 < n; ++i2) {
                for (int j2 = 0; j2 < n; ++j2) {
                    if (!f[i1][j1] || !f[i2][j2]) {
                        continue;
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (!f[i][j]) {
                continue;
            }
            int l = ll[i][j], r = rr[i][j], d = dd[i][j];
            if (get(i, 0, i + 1, l + 1) || get(d, j, n, j + 1) || get(i, r, i + 1, n)) {
                check = false;
            }
            if (l > -1 && d < n) {
                if (get(d, 0, n, l + 1)) {
                    check = false;
                }
            }
            if (r < n && d < n) {
                if (get(d, r, n, n)) {
                    check = false;
                }
            }
        }
    }
    if (check) {
        return pr_sum[n][n];
    } else {
        return pr_sum[n][n] - 1;
    }
}