题目描述

薯条哥是一名数学爱好者，对数论有浓厚的兴趣。最近，他在研究一种奇特的数字性质，叫做 $k-好数$。

他发现，如果一个数可以表示为若干个不同的 $k$ 的幂之和，那么它就是一个 $k-好数$。

例如，$17$ 就是一个 $4-好数$，因为它可以表示为 $4^2+4^0$。但是，$8$ 不是一个 $4-好数$，因为它只能表示为 $4^1+4^1$。

薯条哥一直在思考如何判断一个数是否是 $k-好数$，并找到了一种有效的方法。

他现在想进一步研究 $k-好数$ 在区间 $[l,r]$ 中的分布情况。

他想编写一个程序来解决这个问题，但是他需要一些帮助才能开始。他打算对程序进行 $q$ 次询问，每次询问一个区间 $[l,r]$ 中有多少个 $k-好数$。

输入描述

第一行输入一个正整数 $q(1\le q\le 10^3)$ ，代表询问的次数。

接下来的 $q$ 行，每行输入三个正整数 $l,r,k(1\le l,r\le 10^{12},2\le k\le 10^9)$ ,代表一次询问。

输出描述

输出$q$行，每行输出一个整数，对应一次询问。

样例

输入

2
2 9 3
1 25 4

输出

3
7