def get_mobius(N):
    prime_vals = []
    flag = [True] * (N+1)
    mobius = [0] * (N+1)
    mobius[1] = 1

    for val in range(2, N+1):
        if flag[val]:
            prime_vals.append(val)
            mobius[val] = -1


        for p_val in prime_vals:
            if val * p_val > N:
                break

            flag[val * p_val] = False

            if val % p_val == 0:

                mobius[val * p_val] = 0
                break
            else:
                mobius[val * p_val] = 0 - mobius[val]

    return mobius

# 莫比乌斯函数的前缀和
M = get_mobius(50010)
for i in range(2, 50010):
    M[i] += M[i-1]

# x小于等于A, y小于等于B，最大公约数是d的数对(x, y)的数量
# 定义F(d)为x <= A 且 y <= B的最大公约数是d的倍数的数对(x, y)的个数
# 用倍数来反演的函数f(n)定义为x <= A 且 y <= B的最大公约数是n的数对(x, y)的个数
# 满足F(d)  = f(1d) + f(2d) + f(3d) + ......
# 因为F比较好求，所以用根据莫比乌斯反举定理用F来求f
# F(d)求法就是 (A // d) * (B // d), 根据整数分块的规律，这个函数是一个关于d的分段递减函数，进行分段求解结合莫比乌斯函数的前缀和来做累加即可
def f(A, B, d):
    A, B = A//d, B//d

    if A == 0 or B == 0:
        return 0

    tot = 0
    i = 1
    while True:
        aa, bb = A // i, B // i
        if aa == 0 or bb == 0:
            break

        a_end, b_end = A // (A // i), B // (B // i)
        end = min(a_end, b_end)

        tot += (M[end] - M[i-1]) * aa * bb
        i = end + 1

    return tot

n = int(input())
for _ in range(n):
    a, b, c, d, k = map(int, input().split())
    ans = f(b, d, k) - f(a-1, d, k) - f(b, c-1, k) + f(a-1, c-1, k)
    print(ans)