单点时限: 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$)，含义如题目所述。
对于每组数据输出一行，包含一个整数，表示答案。
2 1 10 2 3 1 100 2 3
1 6
例如，在 $100$ 进制下，末位是 $90$ 的数不算作有末尾 $0$。