#include<bits/stdc++.h>
#define ull long long
using namespace std;
ull a,b,c,d,k,ans,T;
ull count(ull a,ull b,ull k)
{
    ull res;
    if(k>=2*a)res=(2*a+1)*(2*a+1);
    else if(k<=a)res=(2*k+1)*(2*k+1)/2+1;
    else res=(2*a+1)*(2*a+1)-(2*a-k)*(2*a-k+1)*2;
    if(b)res-=count(b,0,k);
    return res;
}
ull get(ull m){return count(d,c,m)+count(c,b,m/2)+count(b,a,m/3)+count(a,0,m/4);}
main()
{
    cin>>T;
    while(T--)
    {
        cin>>a>>b>>c>>d>>k;
        k--;
        ull ans=0;
        for(int i=1;k>0;i++)
        {
            ull tmp=get(i)-get(i-1);
            ans+=min(tmp,k)*i;
            k-=tmp;
        }
        cout<<ans<<endl;
    }
}