Diagnostic 0 : 1

Interview

Time limit2sMemory limit1024 MB

Summary

Count integers k in [a, b] whose base-m digit sum equals n, for up to 50,000 test cases.

Level: Medium5 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

For each positive integer $m$ with $2 \le m$ , define the function $f_{m}$ on the set of non-negative integers as follows.

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

Given positive integers $a$ , $b$ , $m$ , and $n$ , find the number of integers $k$ with $a \le k \le b$ that satisfy $f_{m}(k) = n$ .

Input

The first line contains the number of test cases $T$ . $(1 \le T \le 50\,000)$

Each of the next $T$ lines contains positive integers $a$ , $b$ , $m$ , and $n$ , separated by spaces. $(1 \le a \le b \le 10^{18};$ $2 \le m \le 10;$ $1 \le n \le 100)$

Output

For each test case, print on its own line the number of integers $k$ with $a \le k \le b$ that satisfy $f_{m}(k) = n$ , using the given $a$ , $b$ , $m$ , and $n$ .

Examples1

Example 1
Input
```
3
1 7 2 2
8 12 3 1
7 17 4 2
```
Expected output
```
3
1
8
```