#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define RD read()
#define PN putchar('\n')
using namespace std;
bool MemoryBegin;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while('0' <= ch && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

int const N = 1e3 + 5;

int f[N][N];

signed main() {
    //cerr << fabs(&MemoryBegin - &MemoryEnd) / 1048576.0 << " MB\n";
    memset(f, 0x3f, sizeof f);
    rep(i, 2, N - 1) f[i][0] = 1;
    rep(i, 1, N - 1) {
        rep(j, 1, N - 1) {
            if(j > 1) f[i][j] = min(f[i][j - 2] + 1, min(f[i - 1][j - 1] + 1, f[i][j - 2] + 2 * (i + j - 2) + 1));
            else f[i][j] = min(f[i - 1][j - 1] + 1, f[i][j - 1] + i);
        }
    }
    int T = RD;
    while(T --) {
        printf("%lld\n", f[RD][RD]);
    }
    // rep(i, 1, 10) {
    //     PN;
    //     rep(j, 1, 10) {
    //         printf("f[%lld][%lld] = %lld\n", i, j, f[i][j]);
    //     }
    // }
    // cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << " ms\n";
    return 0;
}