K ONLY

#define task "KONLY"

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e5 + 5;
constexpr int block = 320;
constexpr ll mod = 220210212116;

int a, b, c, d, k;
int in[N], beg[block], en[block];
ll cnt[N][block];
int var[N];

vector<int> factor[N];

#define bit(i, x) (((x) >> (i)) & 1)

ll Mul(ll a, ll b)
{
    ll q = (ld)a * b / mod;
    ll r = a * b - q * mod;

    return (r % mod + mod) % mod;
}

ll Sum(ll v)
{
    return v * (v + 1) / 2;
}
void Prepare()
{
    for (int i = 1; i < N; ++i)
        factor[i].reserve(8);

    /// Sieve

    for (int i = 2; i < N; ++i)
        if (factor[i].empty())
            for (int j = i; j < N; j += i)
                factor[j].emplace_back(i);

    /// Prepare

    for (int i = 1; i < N; ++i)
    {
        in[i] = i / block + 1;
        if (!beg[in[i]])
            beg[in[i]] = i;
        en[in[i]] = i;
    }

    for (int i = 1; i <= 1e5; ++i)
        for (int j = 1; j <= in[(int)1e5]; ++j)
        {
            cnt[i][j] = Sum(en[j]) % mod;
            var[0] = 1;

            for (int h = 1; h < (1 << factor[i].size()); ++h)
            {
                var[h] = var[h - (h & -h)] * factor[i][__lg(h & -h)];

                (cnt[i][j] += (__builtin_popcount(h) & 1 ? -1 : 1) * Mul(var[h], Sum(en[j] / var[h]))) %= mod;
            }

            cnt[i][j] = (cnt[i - 1][j] + cnt[i][j] * i) % mod;
        }
}

void Read()
{
    cin >> a >> b >> c >> d >> k;

    a = (a + k - 1) / k;
    b /= k;
    c = (c + k - 1) / k;
    d /= k;
}


ll f(int u, int v)
{
    if (u == 0 || v == 0)
        return 0;

    if (u > v)
        swap(u, v);

    ll ans(cnt[v][in[u] - 1]);

    for (int i = beg[in[u]]; i <= u; ++i)
    {
        ll res = Sum(v) % mod;
        var[0] = 1;

        for (int j = 1; j < (1 << factor[i].size()); ++j)
        {

            var[j] = var[j - (j & -j)] * factor[i][__lg(j & -j)];

            (res += (__builtin_popcount(j) & 1 ? -1 : 1) * Mul(var[j], Sum(v / var[j])) ) %= mod;
        }

        ans = (ans + res * i) % mod;
    }

    return ans;
}


void Solve()
{
    cout << ((f(b, d) - f(a - 1, d) - f(b, c - 1) + f(a - 1, c - 1)) % mod * k % mod * k % mod + mod) % mod << "\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Prepare();

    int t;
    for (cin >> t; t--;)
    {
        Read();
        Solve();
    }
}