Problem #3679 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

“他觉得一个人奋斗更轻松自在。跟没有干劲的人在一起厮混，只会徒增压力。”

QQ 小方决定一个人研究研究进制转换。

很快，QQ 小方就遇到问题了。他现在想知道在十进制范围 $[l, r]$ 内有多少整数满足在 $k$ 进制下末尾恰好有 $m$ 个 $0$ 。

比如在十进制下的 $24$ 在二进制下是 $11000$ ，我们称十进制下的 $24$ 在二进制下末尾恰好有 $3$ 个 $0$ 。

QQ 小方一筹莫展，你能帮他解决问题吗？

第一行包含一个整数 $T$ ( $1 \leq T \leq 10^{5}$ ) 表示数据组数。

对于每组数据包含一行，四个整数 $l, r, k, m$ ( $1 \leq l \leq r \leq 10^{18}$ , $2 \leq k, m \leq 100$ )，含义如题目所述。

对于每组数据输出一行，包含一个整数，表示答案。

Input

2
1 10 2 3
1 100 2 3

Output

1
6

例如，在 $100$ 进制下，末位是 $90$ 的数不算作有末尾 $0$ 。

356 人解决，628 人已尝试。

476 份提交通过，共有 3461 份提交。

3.5 EMB 奖励。

创建: 6 年，1 月前.

修改: 1 月前.

最后提交: 1 周，4 天前.

3679. 进制转换