暂无测试数据。

蒜头君在 $[2,10^9]$ 内选择了一个数 $x$ 作为基数，想要通过这个基数得到他的幸运数字。假设蒜头君的幸运数字为 $n$，那么 $n = bx^k$ 表示幸运数字 $n$ 的神奇形式，其中 $b,k$ 为任意非负整数。当然，幸运数字 $n$ 可能有多种神奇形式。

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

输入格式

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

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

输出格式

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

数据范围

• 对于 $30\%$ 的数据，满足 $T=1,1\leq r\leq 10^6$。
• 对于 $50\%$ 的数据，满足 $T=1,1\leq r\leq 10^9$。
• 对于 $100\%$ 的数据，满足 $1\leq T\leq 10^5,1\leq l\leq r\leq 10^9,2\leq x\leq 10^9$。

2
3 10 2
30 55 3

3
3

3
10 100 3
12 435 16
33242 43534 23

4
2
3