有N个战士需要装备武器，但是数量不够，小A是个魔法师，他能施法干二件事：

1、将武器数量加1
2、将每件武器复制位K件，即可武器总数乘以K。

小A 想知道，他最少需要使用多少次魔法才能使武器数刚好等于战士数N。

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

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

样例解释： 对于第一组数据，可以连续使用2次魔法1，即1->2->3(数字表示使用魔法后的武器数) 对于第二组数据，可以连续使用3次魔法2后再只用一次魔法1，即1->2->4->8->9。 数据范围： 对于 20% 的数据，k,n≤10；

对于 30% 的数据，k,n≤100；

对于另外 20% 的数据，所有的 k 都相同且n≤10^8 ；

对于另外 20% 的数据，k≤2；

对于 100% 的数据，1≤T≤10^6 ,1≤k,n≤10^18 。