#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 35;

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

struct Queue_max {
    vector<pair<int, int>> st1, max1, st2, max2;

    Queue_max() {
        max1.push_back({0, 0});
        max2.push_back({0, 0});
    }

    void push(pair<int, int> p) {
        st1.push_back(p);
        max1.push_back(max(max1.back(), st1.back()));
    }

    pair<int, int> get_max() {
        return max(max1.back(), max2.back());
    }

    pair<int, int> front() {
        if (!st2.empty()) {
            return st2.back();
        }
        return st1[0];
    }

    void pop() {
        if (st2.empty()) {
            while (!st1.empty()) {
                st2.push_back(st1.back());
                max2.push_back(max(max2.back(), st2.back()));
                st1.pop_back();
                max1.pop_back();
            }
        }
        st2.pop_back();
        max2.pop_back();
    }

    bool empty() {
        return st1.empty() && st2.empty();
    }
};

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) {
                if (i > 0) {
                    Queue_max ql, qr;
                    for (int l2 = 0; l2 < n; ++l2) {
                        if (dp[i][i + width - 1][l2] != 0) {
                            qr.push({dp[i][i + width - 1][l2], r[i][i + width - 1][l2]});
                        }
                        if (!get(i - 1, l2, i, l2 + 1)) {
                            continue;
                        }
                        int r2 = rr[i - 1][l2];
                        while (!qr.empty() && qr.front().second < r2) {
                            ql.push({qr.front().first + qr.front().second, qr.front().second});
                            qr.pop();
                        }
                        while (!ql.empty() && ql.front().second <= l2) {
                            ql.pop();
                        }
                        if (!qr.empty() && dp[i - 1][i + width - 1][l2] < qr.get_max().first + r2 - l2) {
                            r[i - 1][i + width - 1][l2] = r2;
                            dp[i - 1][i + width - 1][l2] = qr.get_max().first + r2 - l2;
                            ans = max(ans, dp[i - 1][i + width - 1][l2]);
                        }
                        if (!ql.empty() && dp[i - 1][i + width - 1][l2] < ql.get_max().first - l2) {
                            r[i - 1][i + width - 1][l2] = ql.get_max().second;
                            dp[i - 1][i + width - 1][l2] = ql.get_max().first - l2;
                            ans = max(ans, dp[i - 1][i + width - 1][l2]);
                        }
                    }
                }
                if (i + width < n) {
                    Queue_max ql, qr;
                    for (int l2 = 0; l2 < n; ++l2) {
                        if (dp[i][i + width - 1][l2] != 0) {
                            qr.push({dp[i][i + width - 1][l2], r[i][i + width - 1][l2]});
                        }
                        if (!get(i + width, l2, i + width + 1, l2 + 1)) {
                            continue;
                        }
                        int r2 = rr[i + width][l2];
                        while (!qr.empty() && qr.front().second < r2) {
                            ql.push({qr.front().first + qr.front().second, qr.front().second});
                            qr.pop();
                        }
                        while (!ql.empty() && ql.front().second <= l2) {
                            ql.pop();
                        }
                        if (!qr.empty() && dp[i][i + width][l2] < qr.get_max().first + r2 - l2) {
                            r[i][i + width][l2] = r2;
                            dp[i][i + width][l2] = qr.get_max().first + r2 - l2;
                            ans = max(ans, dp[i][i + width][l2]);
                        }
                        if (!ql.empty() && dp[i][i + width][l2] < ql.get_max().first - l2) {
                            r[i][i + width][l2] = ql.get_max().second;
                            dp[i][i + width][l2] = ql.get_max().first - 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;
    }
}