如果一个数是k-精简数那么他在k进制下只包含0和1，进行数位DP即可
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
题目内容
小蓝在研究进制转换时发现了一种有趣的数：对于一个给定的基数 K，如果一个正整数在 K 进制下的表示中只包含数字 0 和 1，那么它被称为 K-精简数。例如 17 在 4 进制下写作 101，所以它是 4-精简数；而 8 在 4 进制下写作 20，不是 4-精简数。
现在有 q 个询问，每个询问给定一个区间 [l,r] 与基数 k，请你回答区间内有多少个 k-精简数。
询问次数 q 不超过 1000。区间左端点 l 和右端点 r 的取值范围是 1 到 10^{12}（包含边界），且保证 l≤r。基数 k 的取值范围是 2 到 10^9。
输入描述
第一行包含一个整数 q，代表询问的次数。
接下来的 q 行，每行包含三个整数 l，r，k，依次表示区间的左端点、右端点和给定基数。
输出描述
共 q 行，每行输出一个整数，表示对应区间中 k-精简数的数量。
样例1
输入
2
2 9 3
1 25 4
输出
3
7
说明
基数 $k=3$ 时，区间 $[2,9]$ 中的 $3$-好数 有 $3$（$10_3$）、$4$（$11_3$）、$9$（$100_3$），共 $3$ 个；基数 $k=4$ 时，区间 $[1,25]$ 中的 $4$-好数 有 $1,4,5,16,17,20,21$，共 $7$ 个。
样例2
输入
1
1 10 3
输出
5
说明
基数 $k=3$。逐一检查 1 到 10 的三进制表示：1 写作 1（有效）；2 写作 2（无效）；3 写作 10（有效）；4 写作 11（有效）；5 写作 12（无效）；6 写作 20（无效）；7 写作 21（无效）；8 写作 22（无效）；9 写作 100（有效）；10 写作 101（有效）。满足只含 0 和 1 的数有 1、3、4、9、10，共 5 个 $3$-好数。
样例3
输入
2
1 100 10
4 4 3
输出
4
1
说明
第一个询问基数 $k=10$，十进制下只含 0 和 1 的数在 $[1, 100]$ 内有 1、10、11、100，共 4 个 $10$-好数。第二个询问区间 $[4, 4]$，基数 $k=3$，4 的三进制为 11，是 $3$-好数，结果为 1。
TaZi