2702

2702. problem b

题目

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

输入格式

第一行一个整数 $n$。

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

输出格式

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

数据范围

$1 \le n \le 50000$,

$1 \le a \le b \le 50000$,

$1 \le c \le d \le 50000$,

$1 \le k \le 50000$

输入样例：

2
2 5 1 5 1
1 5 1 5 2

输出样例：

14
3

题解