Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

A. Find Minimum Operations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers n and k.

In one operation, you can subtract any power of k from n. Formally, in one operation, you can replace n by (nkx) for any non-negative integer x.

Find the minimum number of operations required to make n equal to 0.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1t104). The description of the test cases follows.

The only line of each test case contains two integers n and k (1n,k109).

Output

For each test case, output the minimum number of operations on a new line.

Example
Input
6
5 2
3 5
16 4
100 3
6492 10
10 1
Output
2
3
1
4
21
10
Note

In the first test case, n=5 and k=2. We can perform the following sequence of operations:

  1. Subtract 20=1 from 5. The current value of n becomes 51=4.
  2. Subtract 22=4 from 4. The current value of n becomes 44=0.

It can be shown that there is no way to make n equal to 0 in less than 2 operations. Thus, 2 is the answer.

In the second test case, n=3 and k=5. We can perform the following sequence of operations:

  1. Subtract 50=1 from 3. The current value of n becomes 31=2.
  2. Subtract 50=1 from 2. The current value of n becomes 21=1.
  3. Subtract 50=1 from 1. The current value of n becomes 11=0.

It can be shown that there is no way to make n equal to 0 in less than 3 operations. Thus, 3 is the answer.