如果一个数是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。
输入描述
