#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
    x=0; char c=getchar(); int f=1;
    while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
    while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
mt19937 R(chrono::system_clock().now().time_since_epoch().count());

//const int N = ;
ll a[166],k;
ll calc1(ll n, ll lim){//cnt
    if(lim>=n+n)return 1ll*(n*2+1)*(n*2+1);
    if(lim>=n)return ((1ll*(n*2+1)*(n*2+1)-2ll*((2*n-lim))*((2*n-lim+1))));
    return (2*(lim)*(lim+1)+1);
}
ll sum1(ll n){return n*(n+1)/2;}
ll sum2(ll n){return n*(n+1)*(2*n+1)/6;}
ll calc2(ll n, ll lim){//sum
    ll cur=2ll*(n)*(n+1)*(2*n+1);
    if(lim>=n+n)return cur;
    if(lim>=n)return (cur-4ll*((1+2*n)*sum1(2*n-lim)-sum2(2*n-lim)));
    return 4*sum2(lim);
}
int main() {
    int t;read(t);while(t--){
        rep(i,1,4)read(a[i]);read(k);
        ll res=6e18;
        ll l=0,r=8ll*a[4];
        ll z=0,w=0,pos=0;
        while(l<=r){
            ll mid=(l+r)>>1;
            ll x=0,y=0;
            rep(i,1,4)x+=calc1(a[i],mid/(5-i))-(i>1?calc1(a[i-1],mid/(5-i)):0);
            rep(i,1,4)y+=(calc2(a[i],mid/(5-i))-(i>1?calc2(a[i-1],mid/(5-i)):0))*(5-i);
            if(x>k)r=mid-1;
            else{z=x;w=y;pos=mid;l=mid+1;}
        }
    //    cerr<<z<<' '<<w<<' '<<pos<<endl;
        res=(k-z)*(pos+1)+w;
        cout<<res<<endl;
    }
    return 0;
}