对于给出的 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) 的个数。

对于 100% 的数据满足：1≤n,k≤5×10⁴，1≤a≤b≤5×10⁴，1≤c≤d≤5×10⁴。

莫比乌斯反演