Description

For each of the given $n$ queries, count the number of pairs $(x,y)$ such that $a \le x \le b$, $c \le y \le d$, and $\gcd(x,y) = k$. The function $\gcd(x,y)$ denotes the greatest common divisor of $x$ and $y$.

Input Format

The first line contains an integer $n$. Each of the next $n$ lines contains five integers, denoting $a, b, c, d, k$.

Output Format

Output $n$ lines, each containing one integer representing the number of pairs $(x,y)$ that satisfy the conditions.

2
2 5 1 5 1
1 5 1 5 2

14
3

Hint

Constraints: For $100\%$ of the testdata, the following holds: $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$.

Translated by ChatGPT 5