#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
    t=0; char ch=getchar(); int f=1;
    while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const ll INF=1e18;
int T;
ll a,b,c,d,k,ans,tmp;
ll C2(ll x) {
    return x*(x+1)/2;
}
ll cnt(ll A,ll B) {
    ll res;
    if (B*2<=A) res=B*B;
    else if (B<=A) res=B*B-C2(B*2-A);
    else res=C2(A-1);
    res+=min(A,B);
    return res*4+1;
}
ll cnt(ll mid) {
    if (mid<0) return 0;
    ll res=cnt(mid,d)-cnt(mid,c);
    res+=cnt(mid/2,c)-cnt(mid/2,b);
    res+=cnt(mid/3,b)-cnt(mid/3,a);
    res+=cnt(mid/4,a);
    return res;
}
ll s1(ll x) { return x*(x+1)/2; }
ll s1(ll l,ll r) { return s1(r)-s1(l-1); }
ll s2(ll x) { return x*(x+1)*(2*x+1)/6; }
ll s2(ll l,ll r) { return s2(r)-s2(l-1); }
ll sum(ll A,ll B) {
    ll res,l,r;
    if (B*2<=A) res=B*C2(B);
    else if (B<=A) {
        l=A-B+1,r=B;
        res=C2(A-B)*B+A*s1(l,r)-s2(l,r);
    } else {
        l=1,r=A-1;
        res=A*s1(l,r)-s2(l,r);
    }
    res*=2;
    res+=C2(min(A,B));
    return res*4;
}
ll sum(ll mid) {
    if (mid<0) return 0;
    ll res=sum(mid,d)-sum(mid,c);
    res+=(sum(mid/2,c)-sum(mid/2,b))*2;
    res+=(sum(mid/3,b)-sum(mid/3,a))*3;
    res+=sum(mid/4,a)*4;
    return res;
}
int main() {
    //freopen("1.txt","r",stdin);
    ll l,r,mid,res;
    read(T);
    while (T--) {
        read(a); read(b); read(c); read(d); read(k);
        if (!k) { printf("0\n"); continue; }
        l=0,r=(ll)(1e10);
        while (l<=r) {
            mid=(l+r)/2;
            if (cnt(mid)>=k) res=mid,r=mid-1;
            else l=mid+1;
        }
        //printf("%lld\n",res);
        tmp=k-cnt(res-1);
        ans=tmp*res;
        ans+=sum(res-1);
        printf("%lld\n",ans);
    }
    return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Interger overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/