K ONLY

#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;
int a, b, c, d, k;
int in[N], beg[block], en[block];
ll cnt[N][block];

vector<int> factor[N];

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

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 <= 1e5; ++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] = cnt[i - 1][j];

            cnt[i][j] += en[j];

            for (int h = 1; h < (1 << factor[i].size()); ++h)
            {
                int var(1),
                    sign(__builtin_popcount(h) & 1 ? -1 : 1);

                for (int t = 0; t < (int)factor[i].size(); ++t)
                    if (bit(t, h))
                        var *= factor[i][t];

                cnt[i][j] += sign * (en[j] / var);
            }
        }
}

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)
    {
        ans += v;
        for (int j = 1; j < (1 << factor[i].size()); ++j)
        {
            int var(1),
                sign(__builtin_popcount(j) & 1 ? -1 : 1);

            for (int t = 0; t < (int)factor[i].size(); ++t)
                if (bit(t, j))
                    var *= factor[i][t];

            ans += sign * (v / var);
        }
    }

    return ans;
}

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

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Prepare();

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