A. 幸运数字

小途在 内选择了一个数 x 作为基数，想要通过这个基数得到他的幸运数字。假设小途的幸运数字为 n，那么 表示幸运数字 n 的神奇形式，其中 b,k 为任意非负整数。当然，幸运数字 n 可能有多种神奇形式。

现在你有 T 个问题，每个问题形如：在 [l,r] 区间内的所有幸运数字的所有神奇形式中，k 的最大值是多少？

第一行一个整数 T 表示询问个数。

下面 T 行每行三个整数 l,r,x 表示一次询问。

输出 T 行，每行一个整数表示 k 的最大值。

样例输入1

2
3 10 2
30 55 3

样例输出1

3
3

样例解释1

对于第一个询问，8 的神奇形式为 ，k 值为 3，可以证明不存在更大的 k 值。

对于第二个询问，54 的神奇形式为 ，k 值为 3，可以证明不存在更大的 k 值。

样例输入2

3
10 100 3
12 435 16
33242 43534 23

样例输出2

4
2
3

样例解释2

对于第一个询问，81 的神奇形式为 ，k 值为 4，可以证明不存在更大的 k 值。

对于第二个询问，256 的神奇形式为 ，k 值为 2，可以证明不存在更大的 k 值。

对于第三个询问，36501 的神奇形式为 ，k 值为 3，可以证明不存在更大的 k 值。

对于 30% 的数据，满足 。

对于 50% 的数据，满足 。

对于 100% 的数据，满足 。