#include<bits/stdc++.h>
using namespace std;

#define ll long long
ll sum1(ll x){return x * (x + 1) / 2;}
ll sum2(ll x){return x * (x + 1) * (2 * x + 1) / 6;}
ll sum1(ll l , ll r){return sum1(r) - sum1(l - 1);}
ll sum2(ll l , ll r){return sum2(r) - sum2(l - 1);}

ll calcnum(ll rec , ll lim){
    if(lim >= 2 * rec) return (2 * rec + 1) * (2 * rec + 1);
    if(lim <= rec) return 2 * lim + 1 + 2 * (sum1(lim) * 2 - lim);
    return (2 * rec + 1) * (2 * rec + 1) - sum1(2 * rec - lim) * 4;
}

ll sums(ll l , ll r){return 2 * (sum2(l , r) - (l - 1) * sum1(l , r));}

ll calcsum(ll rec , ll lim){
    if(lim >= 2 * rec) return sum1(rec) * 2 * (2 * rec + 1) * 2;
    if(lim <= rec) return 4 * (-2 * sum2(lim) + (2 * lim + 1) * sum1(lim));
    return sum1(rec) * 2 * (2 * rec + 1) * 2 - sums(lim - rec + 1 , rec) * 4;
}

ll T , len[4] , K;

int main(){
    for(cin >> T ; T ; --T){
        cin >> len[0] >> len[1] >> len[2] >> len[3] >> K; if(K == 1){puts("0"); continue;}
        ll L = 0 , R = 1e12;
        while(L < R){
            ll mid = (L + R) >> 1 , sum = 0;
            for(int i = 0 ; i < 4 ; ++i) sum += calcnum(len[i] , mid / (4 - i)) - (i ? calcnum(len[i - 1] , mid / (4 - i)) : 0);
            sum >= K ? R = mid : L = mid + 1;
        }
        ll ans = 0;
        for(int i = 0 ; i < 4 ; ++i){
            K -= calcnum(len[i] , (L - 1) / (4 - i)) - (i ? calcnum(len[i - 1] , (L - 1) / (4 - i)) : 0);
            ans += (calcsum(len[i] , (L - 1) / (4 - i)) - (i ? calcsum(len[i - 1] , (L - 1) / (4 - i)) : 0)) * (4 - i);
        }
        cout << ans + K * L << endl;
    }
    return 0;
}