3679. 进制转换

单点时限: 2.0 sec

内存限制: 256 MB

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

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

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

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

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

输入格式

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

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

输出格式

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

样例

Input
2
1 10 2 3
1 100 2 3
Output
1
6

提示

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

324 人解决,568 人已尝试。

430 份提交通过,共有 3128 份提交。

3.6 EMB 奖励。

创建: 1 年,5 月前.

修改: 1 年,5 月前.

最后提交: 5 天,16 小时前.

来源: EOJ Monthly 2019.2

题目标签