#include <iostream>
#include <cstdio>

const int N = int(3e5), M = 900, K = int(120);

using namespace std;

long long t, m, ur[M + 1], pir[K + 1],dp[N + 1];

int main() {
    ur[1] = 1;
    for (int i = 2; i <= M; i++)
        ur[i] = ur[i - 1] + i;

    pir[1] = 1;
    for (int i = 2; i <= M; i++)
        pir[i] = pir[i - 1] + ur[i];

    dp[1] = 1;

    for (int i = 2; i <= N; i++)
        dp[i] = -1;

    for (int i = 2; i <= K; i++)
        dp[ pir[i] ] = 1;

    for (int i = 2; i <= N; i++)   {
        for (int j = 1; j <= K; j++) {
            if (dp[i] != -1 && i + pir[j] <= N && ( dp[i + pir[j] ] == -1 || dp[i + pir[j] ] > dp[i] + 1 ) )
                dp[i + pir[j] ] = dp[i] + 1;
        }
    }

    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> m;
        cout << dp[m] << endl;
    }

    return 0;
}