You are given an integer n and an integer k.

In one step you can do one of the following moves: 

  * decrease n by 1; 
  * divide n by k if n is divisible by k. 



For example, if n = 27 and k = 3 you can do the following steps: 27 → 26 → 25 → 24 → 8 → 7 → 6 → 2 → 1 → 0.

You are asked to calculate the minimum number of steps to reach 0 from n. 

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of queries.

The only line of each query contains two integers n and k (1 ≤ n ≤ 10^{18}, 2 ≤ k ≤ 10^{18}).

Output

For each query print the minimum number of steps to reach 0 from n in single line. 

Example

Input


2
59 3
1000000000000000000 10


Output


8
19

Note

Steps for the first test case are: 59 → 58 → 57 → 19 → 18 → 6 → 2 → 1 → 0.

In the second test case you have to divide n by k 18 times and then decrease n by 1.


import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class subahswim
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner sc = new Scanner(System.in);
	    int noq = sc.nextInt();
	    String[] n = new String[noq];
	    String[] k = new String[noq];
	    long[] ni = new long[noq];
	    long[] ki = new long[noq];
	    long[] count = new long[noq];
	    long b = 0;
	    
	    for(int i=0;i<noq;i++)
	    {
	        n[i] = sc.next();
	        ni[i] = Long.parseLong(n[i]);
	        k[i] = sc.next();
	        ki[i] = Long.parseLong(k[i]);
	        while(ni[i]>=1)
	    {
	        b = ni[i]%ki[i];
	        if(b == 0)
	        {
	            ni[i] = ni[i]/ki[i];
	            count[i] = count[i] + 1;
	        }
	        else
	        {
	            ni[i]=ni[i]-b;
	            count[i] = count[i] + b;
	        }
	        
	    }
	    System.out.println(count[i]);
	    }
	}
}