【题目描述】

对于给出的 n 个询问，每次求有多少个数对 (x,y)，满足 a≤x≤b，c≤y≤d，且 gcd(x,y)=k，gcd(x,y) 函数为 x 和 y 的最大公约数。

【输入格式】

第一行一个整数 n，接下来 n 行每行五个整数，分别表示 a,b,c,d,k。

【输出格式】

共 n 行，每行一个整数表示满足要求的数对 (x,y) 的个数。

【样例输入】

2
2 5 1 5 1
1 5 1 5 2

【样例输出】

14
3

【数据范围】

10% 的数据满足：1≤n≤5，1≤a≤b≤100，1≤c≤d≤100。

30% 的数据满足：1≤n≤10。

100% 的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000。