#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int t; cin >> t;
    while(t--){
        long long n; cin >> n;
        long long ans = 0;
        while(n){
            // find largest x s.t. 3*x <= n
            long long x = n/3;
            if(x==0) x = 1; // for n=1 or 2, we still need a deal
            long long w = 3*x;
            long long c = 3*x*x + 2*x + 1;
            long long d = n / w;
            if(d==0){ // if largest deal bigger than n
                d = 1;
                w = n; // buy remaining watermelons
                c = 3*d*d + 2*d + 1; // cost formula, works for small d
            }
            ans += d * c;
            n -= d * w;
        }
        cout << ans << "\n";
    }
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBjaW4udGllKDApOwogICAgaW50IHQ7IGNpbiA+PiB0OwogICAgd2hpbGUodC0tKXsKICAgICAgICBsb25nIGxvbmcgbjsgY2luID4+IG47CiAgICAgICAgbG9uZyBsb25nIGFucyA9IDA7CiAgICAgICAgd2hpbGUobil7CiAgICAgICAgICAgIC8vIGZpbmQgbGFyZ2VzdCB4IHMudC4gMyp4IDw9IG4KICAgICAgICAgICAgbG9uZyBsb25nIHggPSBuLzM7CiAgICAgICAgICAgIGlmKHg9PTApIHggPSAxOyAvLyBmb3Igbj0xIG9yIDIsIHdlIHN0aWxsIG5lZWQgYSBkZWFsCiAgICAgICAgICAgIGxvbmcgbG9uZyB3ID0gMyp4OwogICAgICAgICAgICBsb25nIGxvbmcgYyA9IDMqeCp4ICsgMip4ICsgMTsKICAgICAgICAgICAgbG9uZyBsb25nIGQgPSBuIC8gdzsKICAgICAgICAgICAgaWYoZD09MCl7IC8vIGlmIGxhcmdlc3QgZGVhbCBiaWdnZXIgdGhhbiBuCiAgICAgICAgICAgICAgICBkID0gMTsKICAgICAgICAgICAgICAgIHcgPSBuOyAvLyBidXkgcmVtYWluaW5nIHdhdGVybWVsb25zCiAgICAgICAgICAgICAgICBjID0gMypkKmQgKyAyKmQgKyAxOyAvLyBjb3N0IGZvcm11bGEsIHdvcmtzIGZvciBzbWFsbCBkCiAgICAgICAgICAgIH0KICAgICAgICAgICAgYW5zICs9IGQgKiBjOwogICAgICAgICAgICBuIC09IGQgKiB3OwogICAgICAgIH0KICAgICAgICBjb3V0IDw8IGFucyA8PCAiXG4iOwogICAgfQp9Cg==

NwoxCjMKOAoyCjEwCjIwCjI2MDAxMDAwMAo=

7
1
3
8
2
10
20
260010000