GCD问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给出区间 [a,b] , [c,d]求有多少对数满足gcd(x,y) = k,a <=x <= b,c <= y <= d 

Input

 

输入一个T(1 <= T <= 100).

接下来的T行,每行五个整数a,b,c,d,k(1 <= a <= b <= 50000,1 <= c <= d <=50000,1 <= k <= 50000)

Output

 

输出T行,每行一个整数代表对应输入的答案。

Sample Input

2
384 31270 278 37299 70
336 35722 493 16985 158

Sample Output

141647
14170

Hint

 

Source