진단 0 : 1

$2$ 이상의 양의 정수 $m$마다, 음이 아닌 정수 집합을 정의역으로 하는 함수 $f_{m}$을 다음과 같이 정의한다.

$f_{m}(x) = \begin{cases} 0 & (x = 0) \\ f_{m}\left(\dfrac{x}{m}\right) & (x \equiv 0 \pmod {m}) \\ f_{m}\left(\left\lfloor\dfrac{x}{m}\right\rfloor\right) + 1 & (x \not\equiv 0 \pmod {m}) \end{cases}$

양의 정수 $a$, $b$, $m$, $n$이 주어질 때, $a \le k \le b$인 정수 $k$ 중에서 $f_{m}(k) = n$을 만족하는 것의 개수를 구하여라.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T \le 50\,000)$

다음 $T$개의 줄에 양의 정수 $a$, $b$, $m$, $n$이 공백으로 구분되어 주어진다. $(1 \le a \le b \le 10^{18};$ $2 \le m \le 10;$ $1 \le n \le 100)$

$T$개의 줄에 걸쳐, 각각의 $a$, $b$, $m$, $n$에 대해 $a \le k \le b$에서 $f_{m}(k) = n$인 정수 $k$의 개수를 출력한다.