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.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;
 
 //@Manan Parmar

public class p11 implements Runnable {


    public void run() {
        
        InputReader sc = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
 
        int t=sc.nextInt();

        while(t--!=0)
        {
            long n=sc.nextLong();
            long k=sc.nextLong();
            long sum=0;
            while(n!=0)
            {
                if(n%k==0)
                {
                    n=n/k;
                    sum=sum+1;
                }
                else
                {
                    long x=n%k;
                    sum=sum+x;
                    n=n-x;
                    /*double x1=Math.floor(n/k);
                    long x=(long)x1;
                    long y=x*k;
                    long y2=n-y;
                    sum=sum+y2;
                    n=n-y2;*/
                }
            }
            out.println(sum);
        }


        out.close();
            
    }
 

//========================================================================
    static int count(String s, char c) 
    { 
        int res = 0; 
  
        for (int i=0; i<s.length(); i++) 
        { 
            // checking character in string 
            if (s.charAt(i) == c) 
            res++; 
        }  
        return res; 
    }
    static String addZeros(String str, int n)  
    {  
        for (int i = 0; i < n; i++)  
        {  
            str = "0" + str;  
        }  
        return str; 
    }  
      
    // Function to return the XOR  
    // of the given strings  
    static String getXOR(String a, String b)  
    {  
      
        // Lengths of the given strings  
        int aLen = a.length();  
        int bLen = b.length();  
      
        // Make both the strings of equal lengths  
        // by inserting 0s in the beginning  
        if (aLen > bLen)  
        {  
            a = addZeros(b, aLen - bLen);  
        }  
        else if (bLen > aLen)  
        {  
            a = addZeros(a, bLen - aLen);  
        }  
      
        // Updated length  
        int len = Math.max(aLen, bLen);  
      
        // To store the resultant XOR  
        String res = "";  
          
        for (int i = 0; i < len; i++) 
        {  
            if (a.charAt(i) == b.charAt(i))  
                res += "0";  
            else
                res += "1";  
        }  
        return res;  
    }  
    static class Pair
    {
        int a,b;
        Pair(int aa,int bb)
        {
            a=aa;
            b=bb;
        }
    }
    
    static void sa(int a[],InputReader sc)
    {
        for(int i=0;i<a.length;i++)
        {
            a[i]=sc.nextInt();
        }
        Arrays.sort(a);
    }

    static class PairSort implements Comparator<Pair>
    {
        public int compare(Pair a,Pair b)
        {
            return b.b-a.b;
        }
    }


    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
       
        public int read() {
            if (numChars==-1)
                throw new InputMismatchException();
           
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                }
                catch (IOException e) {
                    throw new InputMismatchException();
                }
               
                if(numChars <= 0)              
                    return -1;
            }
            return buf[curChar++];
        }
     
        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() {
            int c = read();
           
            while(isSpaceChar(c))
                c = read();
           
            int sgn = 1;
           
            if (c == '-') {
                sgn = -1;
                c = read();
            }
           
            int res = 0;
            do {
                if(c<'0'||c>'9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
           
            return res * sgn;
        }
       
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
           
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
                return res * sgn;
        }
       
        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
       
        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));
           
            return res.toString();
        }
     
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
     
        public String next() {
            return readString();
        }
       
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    public static void main(String args[]) throws Exception {
        new Thread(null, new p11(),"Main",1<<27).start();
    }
}