J. Playing With Cat

#include <bits/stdc++.h>
using namespace std;
#define cin(v) for (auto &i : v) cin >> i;
#define cout(v) for (auto &i : v) cout << i << " "; cout<<'\n';
#define ll long long
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define MOD 1000000007
#define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs"<< "\n";

void Warding()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

/*
STOP USING int
*/

void solve(){
    ll n; cin>>n;
    ll l = 0, r = 1e9, best = 0, test = n/9;
    while(l<=r){
        ll mid = l + (r-l)/2;
        (9*(mid*(mid+1)/2) >= n ? r = mid - 1, best = mid : l = mid + 1);
    }
    n -= 9*((best-1)*(best)/2);
    bool flag = (n <= best);
    n -= best;
    flag |= (n >= 0 && n <= 3*best && n % 3 == 0);
    n -= best*3;
    flag |= (n >= 0 && n <= 5*best && n % 5 == 0);
    cout<<(flag ? "YES" : "NO")<<endl;
}

int main()
{
    Warding();
    int TC = 1;
    cin >> TC;
    while (TC--)
    {
        solve();
    }
    Time
}