Hashing

Sanggeun built a hashing function that maps an integer to a value in $0$ through $m-1$:

$h(y) = (a \cdot y + b) \bmod m$

Given integers $x$, $n$, $c$, and $d$, write a program that counts how many of the hash values

$h(x),\ h(x+1),\ \dots,\ h(x+n)$

fall within the interval $[c, d]$.

The first line contains the number of test cases $t$ ($1 \le t \le 10^{5}$).

Each of the next $t$ lines contains the integers $a$, $b$, $x$, $n$, $c$, $d$, $m$ separated by spaces.

• $1 \le m \le 10^{15}$
• $0 \le c \le d < m$
• $0 \le a, b < m$
• $0 \le x + n \le 10^{15}$
• $a \cdot (x + n) + b \le 10^{15}$

Every number in the input is a non-negative integer.

For each test case, output on its own line the number of indices $i$ ($0 \le i \le n$) satisfying $c \le (a \cdot (x + i) + b) \bmod m \le d$.