最大公约数 ### 题目描述 对于给出的 $n$ 个询问，每次求有多少个数对 $(x,y)$，满足 $a \le x \le b$，$c \le y \le d$，且 $\gcd(x,y) = k$，$\gcd(x,y)$ 函数为 $x$ 和 $y$ 的最大公约数。 ### 输入描述 第一行一个整数 $n$，接下来 $n$ 行每行五个整数，分别表示 $a,b,c,d,k$。 其中， $1 \le n,k \le 5 \times 10^4$，$1 \le a \le b \le 5 \times 10^4$，$1 \le c \le d \le 5 \times 10^4$。 ### 输出描述 共 $n$ 行，每行一个整数表示满足要求的数对 $(x,y)$ 的个数。 ### 输入输出样例 #### 示例 1 >输入 ```txt 2 2 5 1 5 1 1 5 1 5 2 ``` >输出 ```txt 14 3 ```