对于给出的 \(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\)

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

$100\text{%}$ 的数据满足： $1\le n\le 50000 $， $1\le a\le b\le 50000$ ， $1\le c\le d\le 50000$ ， $1\le k\le 50000$