3679. 进制转换

单点时限: 2.0 sec

内存限制: 256 MB

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

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

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

比如在十进制下的 在二进制下是 ,我们称十进制下的 在二进制下末尾恰好有

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

输入格式

第一行包含一个整数 () 表示数据组数。

对于每组数据包含一行,四个整数 ( , ),含义如题目所述。

输出格式

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

样例

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

提示

例如,在 进制下,末位是 的数不算作有末尾

300 人解决,538 人已尝试。

394 份提交通过,共有 2954 份提交。

3.7 EMB 奖励。

创建: 9 月,2 周前.

修改: 9 月,2 周前.

最后提交: 3 天,3 小时前.

来源: EOJ Monthly 2019.2

题目标签