蛤蜊从古籍中得知，铸剑的温度越接近 $n$ 度，剑的品质越好。现在，他正在研究他家的铸剑炉，想要铸出全村最好的剑。

启动炉子时，蛤蜊已经添过了一次柴，所以铸剑炉的初始温度为 $m$ 度。此后，蛤蜊每次添柴可以使得铸剑炉的温度提高到原来的 $m$ 倍，即温度变为 $m^2,m^3,\cdots$。

蛤蜊想要知道，他最少需要添多少次柴（包括启动炉子时添的那一次），才能使得铸剑炉的温度最接近 $n$ 度，这样他就能铸出一把品质最好的剑。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T \left(1 \leqq T \leqq 10^5\right)$ 代表数据组数，每组测试数据描述如下：

在一行上输入两个整数 $n,m \left(1 \leqq n, m \leqq 10^9\right)$ 代表最佳铸剑温度、蛤蜊每次添柴可以使得铸剑炉的温度提高的倍数。

输出描述

对于每组测试数据，新起一行。输出一个整数，代表蛤蜊最少需要的添柴次数。

样例

输入样例1

3
7 6
6 2
9 9

输出样例1

1
2
1