#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,len[5],k,l,r,ans,sum,mid,lim;
ll tott(ll x,ll p)//==
{
    if(p==0)return 0;
    if(x<0)return 0;
    if(x>=2*p)return (p*2+1)*(p*2+1);
    if(x<=p)return 1ll+2ll*(x+1)*x;
    return (p*2+1)*(p*2+1)-2ll*(p*2ll-x+1)*(p*2ll-x);
}
ll cntp(ll x){return x*(x+1)*(x*2ll+1)/6ll;}
ll summ(ll x,ll p)
{
    if(p==0)return 0;
    if(x<0)return 0;
    if(x>=2*p)return 2ll*(1+p)*p*(p*2ll+1);
    if(x<=p)return x*(x+1)*(x*2ll+1)/6ll*4ll;
    return 2ll*(1+p)*p*(p*2ll+1)-4ll*(p*(p*2ll-x+1)*(p*2ll-x)-(p*2ll-x)*(p*2ll-x-1)/2ll-cntp(p*2ll-x-1ll));
}
int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        for(int i=1;i<=4;i++)scanf("%lld",&len[i]);
        scanf("%lld",&k);
        l=0;r=1000000;
        while(l<r)
        {
            mid=(l+r)/2;
            ans=sum=0;
            for(int i=1;i<=4;i++)
            {
                lim=mid/(4ll-i+1);
                if(mid%(4ll-i+1)==0)lim--;
                sum+=tott(lim,len[i])-tott(lim,len[i-1]);
                ans+=(4ll-i+1)*(summ(lim,len[i])-summ(lim,len[i-1]));
                //if(mid==5)printf("%d %d %d %d\n",i,lim,tot(lim,len[i]),tot(lim,len[i-1]));
            }
            //printf("%lld %lld %lld\n",mid,sum,ans);
            if(sum>k)r=mid;
            else l=mid+1;
        }
        l--;mid=l;
        ans=sum=0;
        for(int i=1;i<=4;i++)
        {
            lim=mid/(4ll-i+1);
            if(mid%(4ll-i+1)==0)lim--;
            sum+=tott(lim,len[i])-tott(lim,len[i-1]);
            ans+=(4ll-i+1)*(summ(lim,len[i])-summ(lim,len[i-1]));
        }
        printf("%lld\n",ans+mid*(k-sum));
    }
    return 0;
}