塔子哥是一名数学爱好者,对数论有浓厚的兴趣。最近,他在研究一种奇特的数字性质,叫做 k−好数。
他发现,如果一个数可以表示为若干个不同的 k 的幂之和,那么它就是一个 k−好数。
例如,17 就是一个 4−好数,因为它可以表示为 42+40。但是,8 不是一个 4−好数,因为它只能表示为 41+41。
塔子哥一直在思考如何判断一个数是否是 k−好数,并找到了一种有效的方法。
他现在想进一步研究 k−好数 在区间 [l,r] 中的分布情况。
他想编写一个程序来解决这个问题,但是他需要一些帮助才能开始。他打算对程序进行 q 次询问,每次询问一个区间 [l,r] 中有多少个 k−好数。
第一行输入一个正整数 q ,代表询问的次数。
接下来的 q 行,每行输入三个正整数 l , r , k ,代表一次询问。
1≤q≤103
1≤l,r≤1012
2≤k≤109
输出q行,每行输出一个整数,对应一次询问。
输入
2
2 9 3
1 25 4
输出
3
7
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.