[HAOI2011]Problem B

内存限制：256 MB 时间限制：1000 ms

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

样例输入 1

2
2 5 1 5 1
1 5 1 5 2

样例输出 1

14
3

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