CodeChef::CHFNSWAP

#include <bits/stdc++.h>
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

long long work(long long n){
    long double y = n ;
    return (long long)(((-2.0) + (sqrt(4.0 + 8 * (y * y + y)))) / 4.0);
}

long long nc2(long long x){
    return (x*(x-1))/2 ;
}

int main(){
    boost ;
    int t;
    cin >> t;
    while (t--){
        long long n ;
        cin >> n;
        long long sum = (n*(n+1))/2 ;
        if (sum & 1){
            cout << 0 << '\n';
            continue;
        }
        long long x,ans{0} ;
        x = work(n) ;
        ans += n-x ;

        if ((x*(x+1))/2 == sum - (x*(x+1))/2){
            ans += nc2(x) + nc2(n -x) ;
        }
        cout << ans << '\n' ;

    }



    return 0;
}