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 javax.lang.model.util.ElementScanner6;

    import java.io.*;

    public class Main{

        public static void main(String[] args) {

            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            InputReader inp = new InputReader(inputStream);
            PrintWriter out = new PrintWriter(outputStream);
            Solver solver = new Solver();
            solver.solve(inp, out);
            out.close();
            
            }



        static class Solver {


            class Node implements Comparable<Node>{
                int i;
                long c;
            
                Node(int i,long c)
                {
                    this.i=i;
                    this.c=c;


                }

            public int compareTo(Node n)
                {
                    if(this.c==n.c)
                    {
                        return Integer.compare(this.i, n.i);
                    }
                    return Long.compare(this.c, n.c);
                }
            }

            public boolean done(int[] sp,int[] par)
            {
                int root;

                root=findSet(sp[0],par);
                
            for(int i=1;i<sp.length;i++)
            {
                    if(root!=findSet(sp[i], par))
                        return false;
            }
            return true;
            }
        public int findSet(int i,int[] par)
        {
            int x =i;
                boolean flag =false;
                while(par[i]>=0)
                {
                    flag = true;
                    i=par[i];
                }
                if(flag)
                    par[x]=i;
                return i;
        }

        public void unionSet(int i,int j,int[] par)
        {
                int x = findSet(i, par);
                int y = findSet(j, par);
                if(x<y)
                {
                    par[y]=x;
                }
                else
                {
                    par[x]=y;
                }
        }

        public  long pow(long a, long b, long MOD) {
                if (b == 0) {
                    return 1;
                }
                if (b == 1) {
                    return a;
                }
                long val = pow(a, b / 2, MOD);
                if (b % 2 == 0) {
                    return val * val % MOD;
                } else {
                    return val * (val * a % MOD) % MOD;

                }
            
            }


            public void minPrimeFactor(int n,int[] s)
            {
                boolean prime[] = new boolean[n+1];
                Arrays.fill(prime, true);
                s[1]=1;
                s[2]=2;
                for(int i=4;i<=n;i+=2)
                {
                    prime[i]=false;
                    s[i]=2;
                }

                for(int i=3;i<=n;i+=2)
                {
                    if(prime[i])
                    {
                        s[i]=i;
                        for(int j=2*i;j<=n;j+=i)
                        {
                            prime[j]=false;
                            s[j]=i;
                        }
                    }
                }
                
            }

            
            // public void findAllPrime(int n,ArrayList<Node> al,int s[])
            // {
            //     int curr = s[n];
            //     int cnt = 1;
            //     while(n>1)
            //     {
            //         n/=s[n];
            //         if(curr==s[n])
            //         {
            //             cnt++;
            //             continue;

            //         }
            //         Node n1 = new Node(curr,cnt);
            //         al.add(n1);

            //         curr=s[n];
            //         cnt=1;
            //     }
            // }

            

            public int binarySearch(int n,int k)
            {
                int left=1;
                int right=100000000+5;
                int ans=0;
                while(left<=right)
                {
                    int mid = (left+right)/2;
                    if(n/mid>=k)
                    {
                        left = mid+1;
                        ans=mid;
                    }
                    else
                    {
                        right=mid-1;
                    }
                }

                return ans;
            }
            public boolean checkPallindrom(String s)
            {
                char ch[] = s.toCharArray();

                for(int i=0;i<s.length()/2;i++)
                {
                    if(ch[i]!=ch[s.length()-1-i])
                        return false;
                }
                return true;
            }


            public void dfs_util(ArrayList<Integer>[] al,boolean vis[],int x,int lvl[],ArrayList<Integer>[] a)
            {
                    
                vis[x] = true;
                
                // System.out.println("x "+x);
                    for(int i=0;i<al[x].size();i++)
                    {
                        
                        if(!vis[al[x].get(i)])
                        {
                            // System.out.println("s.size "+s.size());
                            lvl[al[x].get(i)]=1^lvl[x];
                            a[lvl[al[x].get(i)]].add(al[x].get(i));
                            dfs_util(al, vis, al[x].get(i),lvl,a);   
                            
                        }    
                        
                    }

                
                
                
                
                return ;
            }

            public void dfs(ArrayList<Integer>[] al, int lvl[],ArrayList<Integer>[] a)
            {
                
                boolean vis[] = new boolean[al.length];
            
                int g =0;
                
                for(int i=0;i<al.length;i++)
                { 
                
                
                        if(!vis[i])
                        {
                            lvl[i]=0;
                            a[lvl[i]].add(i);
                            dfs_util(al,vis,i,lvl,a);
                            
                        }
                    
                }

            


            }

            public void remove(ArrayList<Integer>[] al,int x)
            {
                for(int i=0;i<al.length;i++)
                {
                    for(int j=0;j<al[i].size();j++)
                    {

                        if(al[i].get(j)==x)
                            al[i].remove(j);

                    }
                }
            }

            public long gcd(long a, long b) 
            { 
                if (a == 0) 
                    return b; 
                return gcd(b % a, a); 
            }


            public void printDivisors(long n,ArrayList<Long> al) 
            { 
                // Note that this loop runs till square root 
                for (long i=2; i<=Math.sqrt(n); i++) 
                { 
                    if (n%i==0) 
                    { 
                        // If divisors are equal, print only one 
                        if (n/i == i) 
                        {
                            
                                al.add(i);
                        }
                        
            
                        else // Otherwise print both 
                        {   
                                al.add(i); 
                                al.add(n/i);
                        }
                            
                    } 
                } 
            } 

            public static long constructSegment(long seg[],long arr[], int low,int high,int pos)
            {
                if(low==high)
                {
                    seg[pos] = arr[low]; 
                    return seg[pos];
                }
                int mid = (low+high)/2;
                long t1=constructSegment(seg, arr,low , mid,(2*pos)+1);
                long t2=constructSegment(seg,arr,mid+1,high,(2*pos)+2);
                seg[pos] = t1+t2;
                return seg[pos];

            }
            public static long querySegment(long seg[],int low,int high,int qlow, int qhigh,int pos)
            {
                
                if(qlow<=low&&qhigh>=high)
                {
                    return seg[pos];
                }
                else if(qlow>high||qhigh<low )
                {
                    return 0;
                }
                else{
                    long ans=0;
                    int mid=(low+high)/2;
                    ans+=querySegment(seg,low , mid, qlow, qhigh,  (2*pos)+1);
                    ans+=querySegment(seg, mid+1, high, qlow, qhigh, (2*pos)+2);
                return ans; 
                }

            }
            public static int lcs( char[] X, char[] Y, int m, int n ) 
            { 
                if (m == 0 || n == 0) 
                return 0; 
                if (X[m-1] == Y[n-1]) 
                return 1 + lcs(X, Y, m-1, n-1); 
                else
                return Integer.max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 
            } 

            public static long recursion(long start,long end,long cnt[],int a, int b)
            {

                long min=0;
                long count=0;
                int ans1=-1;
                int ans2=-1;
                int l=0;
                int r=cnt.length-1;
                while(l<=r)
                {
                    int mid=(l+r)/2;
                    if(cnt[mid]>=start)
                    {
                        ans1=mid;
                        r=mid-1;
                    }
                    else
                    {
                        l=mid+1;
                    }
                }

                l=0;
                r=cnt.length-1;
                while(l<=r)
                {
                    int mid=(l+r)/2;
                    if(cnt[mid]<=end)
                    {
                        ans2=mid;
                        l=mid+1;
                    }
                    else
                    {
                        r=mid-1;
                    }
                }
                
                if(ans1==-1||ans2==-1||ans2<ans1)
                {
                    // System.out.println("min1 "+min);
                    min=a;
                    return a;

                }
                else
                {
                    min=b*(end-start+1)*(ans2-ans1+1);
                }
                if(start==end)
                {
                    // System.out.println("min "+min);
                    return min;
                }
                long mid = (end+start)/2;
                min = Long.min(min,recursion(start, mid, cnt, a, b)+recursion(mid+1, end, cnt, a, b));
                // System.out.println("min "+min);
                return min;
            }

        



        

            private void solve(InputReader inp, PrintWriter out1) {
            
                int t = inp.nextInt();
                for(int i=0;i<t;i++)
                {
                    long n = inp.nextLong();
                    long k = inp.nextLong();
                    long count=0;
                    while(n!=0)
                    {
                        if(n%k==0)
                        {
                            n/=k;
                            count++;
                        }
                        else
                        {
                            long t1=n%k;
                            count+=t1;
                            n-=t1;
                        }
                    }
                    System.out.println(count);
                }
          

            }
    }





        static class InputReader {
            BufferedReader reader;
            StringTokenizer tokenizer;

            InputReader(InputStream stream) {
                reader = new BufferedReader(new InputStreamReader(stream), 32768);
                tokenizer = null;
            }

            String next() {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    try {
                        tokenizer = new StringTokenizer(reader.readLine());
                    } catch (IOException e) {
                        throw new RuntimeException(e);
                    }
                }
                return tokenizer.nextToken();
            }

            public int nextInt() {
                return Integer.parseInt(next());
            }

            public long nextLong() {
                return Long.parseLong(next());
            }
        }
    }
    class ele{
        long value;
        long i;
        boolean flag;
        public ele(long value,long i)
        {
            this.value = value;
            this.i=i;
            this.flag = false;
        }
    }