说明

Define a function $f$ as,

$ f(n)=\left\{\begin{aligned}& 1 \quad\quad n=1\\& f(\frac{n}{k}) \quad\quad k\mid n\\& f(n-1) + 1 \quad\quad \text{otherwise}\end{aligned}\right.$

Here $k \mid n$ denotes $n$ is divisible by $k$.

You are given two integers $n, k$, please calculate $f(n)$。

输入格式

The first line contains a single integer $t$ $(1\leq t \leq 10^5) -$ the number of test cases.

Then the descriptions of $t$ test cases follow.

The only line of each test case contains two integers $n, k$ $(2 \leq k < n \leq 10^{18})$.

输出格式

For each test case, print the answer of $f(n)$.

样例

3
5 2
7 4
114514 1551

2
4
1364

提示

In the first test case, $f(5)=f(4) + 1$, $f(4)=f(\frac42)=f(2)$, $f(2)=f(\frac22) = f(1)$, $f(1) = 1$, it is obvious that the answer is $2$.