C~K的传承

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

C~K 准备传承一个知识点,在数论中这算是个初级数论的知识点,中级数论的题目,在组合数学中这算是一个大知识点,现在 C~K 要针对这个知识点出题了:
给出区间 [a, b] 和 [c, d],求有多少对数满足 gcd(x,y) = k。

Input

第一行输入一个 T (1 <= T <= 100),代表组数。
接下来的 T 行,每行五个整数 a, b, c, d, k (1 <= a <= b <= 60000, 1 <= c <= d <= 60000, 1 <= k <= 60000)。

Output

输出 T 行,每行一个整数代表对应输入的答案。题目保证 a <= x <= b, c <= y <= d。

Sample Input

2
20 200 20 200 5
386 1633 526 4896 70

Sample Output

812
680

Hint

Source

【山东理工大学第一届ACM知识挑战赛(机试)】C~K