해싱

상근이는 정수를 $0$부터 $m-1$까지의 값으로 대응시키는 해싱 함수

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

를 만들었다.

정수 $x$, $n$, $c$, $d$가 주어질 때, 해시 값

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

중에서 값이 구간 $[c, d]$ 안에 들어가는 것이 몇 개인지 세는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10^{5}$)가 주어진다.

다음 $t$개의 줄에는 각각 정수 $a$, $b$, $x$, $n$, $c$, $d$, $m$이 공백으로 구분되어 주어진다.

• $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}$

입력으로 주어지는 모든 수는 음이 아닌 정수이다.

각 테스트 케이스마다 $c \le (a \cdot (x + i) + b) \bmod m \le d$ 를 만족하는 $i$ ($0 \le i \le n$)의 개수를 한 줄에 하나씩 출력한다.