#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair

ll read()
{
    ll v = 0, f = 1;
    char c = getchar();
    while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
    while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
    return v * f;
}

ll A[10];
ll k;

ll f(ll a, ll b, ll c)
{
    return (a + a + (c - 1) * b) * c / 2;
}

ll f2(ll a, ll b, ll c, ll d)
{
    return a * d * c + (a + b * d) * (c - 1) * c / 2 + b * (c - 1) * (c) * (c * 2 - 1) / 6;
}

ll cal(ll n)
{
    ll a = A[4], b;
    ll re = 1;
    ll t = min(n / 4, a * 2);
    if (t <= a)
    {
        re += f(4, 4, n / 4);
    } else
    {
        re += f(4, 4, a);
        re += f(a * 4, -4, t - a);
    }

    for (ll i = 3; i >= 1; i--)
    {
        a = A[i + 1];
        b = A[i];
        t = min(n / i, b * 2);
        if (b < a * 2)
        {
            // a + 1 .. b .. a * 2 .. b * 2
            if (t <= a)
                re += 0;
            else
                if (t <= b)
                {
                    re += f(4, 8, t - a);
                } else
                    if (t <= a * 2)
                    {
                        re += f(4, 8, b - a);
                        re += f(b * 4 - (a * 2 - b) * 4, 0, t - b);
                    } else
                        if (t <= b * 2)
                        {
                            re += f(4, 8, b - a);
                            re += f(b * 4 - (a * 2 - b) * 4, 0, a * 2 - b);
                            re += f((b * 2 - a * 2) * 4, -4, t - a * 2);
                        }
        } else
        {
            // a + 1 .. a * 2 .. b .. b * 2
            if (t <= a)
                re += 0;
            else
                if (t <= a * 2)
                {
                    re += f(4, 8, t - a);
                } else
                    if (t <= b)
                    {
                        re += f(4, 8, a * 2 - a);
                        re += f((a * 2 + 1) * 4, 4, t - a * 2);
                    } else
                        if (t <= b * 2)
                        {
                            re += f(4, 8, a * 2 - a);
                            re += f((a * 2 + 1) * 4, 4, b - a * 2);
                            re += f(b * 4, -4, t - b);
                        }
        }
    }
    return re;
}

ll cal2(ll n)
{
    ll a = A[4], b;
    ll re = 0;
    ll t = min(n / 4, a * 2);
    if (t <= a)
    {
        re += f2(4, 4, n / 4, 1) * 4;
    } else
    {
        re += f2(4, 4, a, 1) * 4;
        re += f2(a * 4, -4, t - a, a + 1) * 4;
    }

    for (ll i = 3; i >= 1; i--)
    {
        a = A[i + 1];
        b = A[i];
        t = min(n / i, b * 2);
        if (b < a * 2)
        {
            // a + 1 .. b .. a * 2 .. b * 2
            if (t <= a)
                re += 0;
            else
                if (t <= b)
                {
                    re += f2(4, 8, t - a, a + 1) * i;
                } else
                    if (t <= a * 2)
                    {
                        re += f2(4, 8, b - a, a + 1) * i;
                        re += f2(b * 4 - (a * 2 - b) * 4, 0, t - b, b + 1) * i;
                    } else
                        if (t <= b * 2)
                        {
                            re += f2(4, 8, b - a, a + 1) * i;
                            re += f2(b * 4 - (a * 2 - b) * 4, 0, a * 2 - b, b + 1) * i;
                            re += f2((b * 2 - a * 2) * 4, -4, t - a * 2, a * 2 + 1) * i;
                        }
        } else
        {
            // a + 1 .. a * 2 .. b .. b * 2
            if (t <= a)
                re += 0;
            else
                if (t <= a * 2)
                {
                    re += f2(4, 8, t - a, a + 1) * i;
                } else
                    if (t <= b)
                    {
                        re += f2(4, 8, a * 2 - a, a + 1) * i;
                        re += f2((a * 2 + 1) * 4, 4, t - a * 2, a * 2 + 1) * i;
                    } else
                        if (t <= b * 2)
                        {
                            re += f2(4, 8, a * 2 - a, a + 1) * i;
                            re += f2((a * 2 + 1) * 4, 4, b - a * 2, a * 2 + 1) * i;
                            re += f2(b * 4, -4, t - b, b + 1) * i;
                        }
        }
    }
    return re;
}

int main()
{
    int cas = read();
    while (cas--)
    {
        A[4] = read(), A[3] = read(), A[2] = read(), A[1] = read(), k = read();
        ll l = 0, r = 1e10;
        while (l < r)
        {
            ll mid = (l + r) >> 1;
            if (cal(mid) >= k)
                r = mid;
            else
                l = mid + 1;
        }
        printf("%lld\n", cal2(l) - (cal(l) - k) * l);
    }
}