小H的糖果
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小 H 生日的那一天，有人送给了小 H 1 颗糖果。小 H 觉得自己的糖果太少了，于是他学会了两种魔法：
  1. 使糖果数 +1。
  2. 让每一颗糖果分裂成 k 颗糖果，即让糖果总数乘以 k
小 H 想知道，他最少需要使用多少次魔法才能使糖果数刚好等于小 H 的幸运数字 n。

输入描述:

每个测试点包含多组测试数据。
第一行一个正整数 T，表示数据组数。
接下来共 T 行，每行两个正整数 k,n，含义见题目描述。

输出描述:

共 T 行，每行一个非负整数，表示使糖果数量刚好等于 n 的最少魔法使用次数。
示例1

输入

复制 
3
2 3
2 9
114514 1919810

输出

复制 
2
4
87602

说明

样例解释：
对于第一组数据，可以连续使用2次魔法1，即1->2->3(数字表示使用魔法后的糖果数)
对于第二组数据，可以连续使用3次魔法2后再只用一次魔法1，即1->2->4->8->9。
数据范围：
对于 20% 的数据，k,n \leq 10；
对于 30% 的数据，k,n \leq 100；
对于另外 20% 的数据，所有的 k 都相同且 n \leq 10^8；
对于另外 20% 的数据，k\leq 2；
对于 100% 的数据，1 \leq T \leq 10^6,1 \leq k,n \leq 10^{18}。