#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define inv2 500000004
#define last last2

using namespace std;

typedef long long ll;
typedef __int128 lll;
typedef double db;

inline lll S(lll l,lll r) {
  return (l+r)*(r-l+1)>>1;
}

inline lll S2(lll n) {
  return n*(n+1)*(2*n+1)/6;
}

lll query1(lll n,lll d) {
  lll s=4LL*min(n,d)+1LL;
  if (d>=2LL*n) s+=4LL*n*n;
  else if (d>=n) s+=4LL*(n*(d-n)+S(d-n,n-1));
  else s+=4LL*S(1,d-1);
  return s;
}

lll query2(lll n,lll d) {
  lll s=4LL*S(1,min(n,d));
  if (d>=2LL*n) s+=2LL*4LL*n*S(1,n);
  else if (d>=n) s+=2LL*4LL*(n*S(1,d-n)+S(d-n+1,n)*d-S2(n)+S2(d-n));
  else s+=2LL*4LL*(S(1,d)*d-S2(d));
  return s;
}

lll query1(ll a,ll b,ll c,ll d,ll v) {
  lll s=0;
  s+=query1(a,v/4);
  s+=query1(b,v/3)-query1(a,v/3);
  s+=query1(c,v/2)-query1(b,v/2);
  s+=query1(d,v/1)-query1(c,v/1);
  return s;
}

lll query2(ll a,ll b,ll c,ll d,ll v) {
  lll s=0;
  s+=query2(a,v/4)*4LL;
  s+=(query2(b,v/3)-query2(a,v/3))*3LL;
  s+=(query2(c,v/2)-query2(b,v/2))*2LL;
  s+=(query2(d,v/1)-query2(c,v/1))*1LL;
  return s;
}

int main() {
  int cases;
  scanf("%d",&cases);
  for(;cases;cases--) {
      ll a,b,c,d,k;
      scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
      if (!k) {
          puts("0");
          continue;
      }
      ll l=0,r=1e10;
      while (l<r) {
          ll mid=((l+r)>>1)+1;
          if (query1(a,b,c,d,mid)<=k) l=mid; else r=mid-1;
      }
    ll s1=query2(a,b,c,d,l);
    ll s2=(k-query1(a,b,c,d,l))*(l+1);
    printf("%lld\n",s1+s2);
  }
  return 0;
}