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.io.*;
import java.util.Scanner;
import java.math.*;
import java.lang.StringBuilder;

public class contest
{
   public static void main(String[] args)
   {
      Scanner scan = new Scanner(System.in);
      int t = scan.nextInt();
      long n = 0;
      long k = 0;
      long count = 1;
      for (int i = 0; i < t; i++)
      {
         n = scan.nextLong();
         k = scan.nextLong();
         while (n > 1)
         {
            if (n < k)
            {
               count += n - 2;
               n = 1;
            }
            /*if (n % k < 1)
            {
               n /= k;
            }
            else
            {
               n--;
            }*/
            count += (n % k);
            n -= (n % k);
            if (n > 1)
            {
               n /= k;
               count++;
            }
         }
         System.out.println(count);
         count = 1;
      }
      
      
   }
   
   public static boolean isPrime(int num[], int n)
   {
      if (num[num.length - 1] % 2 == 0)
      {
         return false;
      }
      int c = 0;
      int ten = 1;
      for (int i = 0; i < n; i++)
      {
         c += num[n - 1 - i] * ten;
         ten *= 10;
      }
      for (int i = 3; i * i <= c; i++)
      {
         if (c % i == 0)
         {
            return false;
         }
      }
      return true;
   }
}
   
   /*private static int N;
   private static int M;
   
   public static void main(String[] args)
   {
      Scanner scan = new Scanner(System.in);
      N = scan.nextInt();
      M = scan.nextInt();
      
      LineWrapper lineWrapper = new LineWrapper();
      Line line = new Line(scan.nextInt(), scan.nextInt());
      
      lineWrapper.insert(new Line(line));
      for (int i = 1; i < M; i++)
      {
         lineWrapper.insert(new Line(scan.nextInt(), scan.nextInt()));
      }
      lineWrapper.sort();
      
      String comp = lineWrapper.toString();
      
      ArrayList<Integer> possible = new ArrayList<Integer>();
      
      int adder = 1 + N % 2;
      possible.add(0);
      possible.add(1);
      if (N % 2 == 0)
      {
         possible.add(2);
      }
      for (int i = 3; i < N / 2 + 1; i += adder)
      {
         if (N % i == 0)
         {
            possible.add(i);
         }
      }
      
      int i = 0;
      int j;
      int count = 0;
      
      do
      {
         j = 0;
         do
         {
            if (count > possible.size() - 2)
            {
               System.out.print("No");
               System.exit(0);
            }
            line.rotate(possible.get(count + 1) - possible.get(count) - 1);
            j += possible.get(count + 1) - possible.get(count);
            count++;
         } while (!lineWrapper.contains(line));
         
         lineWrapper.rotate(j - 1);
         line.rotate(j - 1);
         i += j;
      } while (!comp.equals(lineWrapper.toString()));
      
      int incr = i;
      i += incr;
      
      if (i > N)
      {
         System.out.print("No");
         System.exit(0);
      }
      for (; i < incr * 3 && i < N / 2 + 1; i += incr)
      {
         lineWrapper.rotate(incr - 1);
         
         if (!comp.equals(lineWrapper.toString()))
         {
            System.out.print("No");
            System.exit(0);
         }
      }
      System.out.print("Yes");
   }
   public static class LineWrapper
   {
      public ArrayList<Line> list;
      
      public LineWrapper()
      {
         list = new ArrayList<Line>();
      }
      
      public void insert(Line line)
      {
         list.add(line);
      }
      
      public void sort()
      {
         Collections.sort(list);
      }
      
      public void rotate(int incr)
      {
         for (Line line: list)
         {
            line.rotate(incr);
         }
         Collections.sort(list);
      }
      
      public boolean contains(Line line)
      {
         int left = 0;
         int right = M - 1;
         int mid = right / 2;
         int temp;
         while (right - left > 1)
         {
            temp = line.compareTo(list.get(mid));
            if (temp < 0)
            {
               right = mid;
            }
            else if (temp > 0)
            {
               left = mid;
            }
            else
            {
               return true;
            }
            mid = (left + right) / 2;
         }
         if (line.compareTo(list.get(right)) == 0 ||
             line.compareTo(list.get(left)) == 0)
         {
            return true;
         }
         return false;
      }
      
      public String toString()
      {
         StringBuilder s = new StringBuilder("");
         for (Line line: list)
         {
            s.append(line.toString());
         }
         return s.toString();
      }
   }
   public static class Line implements Comparable<Line>
   {
      private int a;
      private int b;
      
      public Line(int ain, int bin)
      {
         a = (ain < bin) ? ain : bin;
         b = (ain < bin) ? bin : ain;
      }
      
      public Line(Line line)
      {
         a = line.getA();
         b = line.getB();
      }
      
      public int getA()
      {
         return a;
      }
      
      public int getB()
      {
         return b;
      }
      
      public void rotate(int incr)
      {
         a = ((a + incr) % N) + 1;
         b = ((b + incr) % N) + 1;
         if (a > b)
         {
            int temp = a;
            a = b;
            b = temp;
         }
      }
      
      public String toString()
      {
         return "" + a + b;
      }
      
      @Override
      public int compareTo(Line line)
      {
         if (a < line.getA())
         {
            return -1;
         }
         if (a > line.getA())
         {
            return 1;
         }
         if (b < line.getB())
         {
            return -1;
         }
         if (b > line.getB())
         {
            return 1;
         }
         return 0;
      }
   }
}
      
/*   
      int A = scan.nextInt();
      int B = scan.nextInt();
      int As[];
      int Bs[];
      //0 = n^2 + n - 2(A + B)
      int N = (int) (-1.0 / 2 + 2 * Math.sqrt(1.0 / 16 + (A + B) / 2.0));
      if (B == 0)
      {
         int i = 0;
         while (A > 0 && N > i)
         {
            A -= (N - i);
            i++;
         }
         As = new int[i];
         for (int j = 0; j < i; j++)
         {
            As[j] = N - j;
         }
         System.out.println(i);
         for (int j = 0; j < i; j++)
         {
            System.out.print(As[j] + " ");
         }
         System.out.println("\n0");
      }
      else if (A == 0)
      {
         int i = 0;
         while (B > 0 && N > i)
         {
            B -= (N - i);
            i++;
         }
         Bs = new int[i];
         for (int j = 0; j < i; j++)
         {
            Bs[j] = N - j;
         }
         System.out.println("0\n");
         System.out.println(i);
         for (int j = 0; j < i; j++)
         {
            System.out.print(Bs[j] + " ");
         }
      }
      else if (A <= B)
      {
         int i = 0;
         while (A > N - i)
         {
            A -= (N - i);
            i++;
         }
         As = new int[i + 1];
         for (int j = 0; j < i; j++)
         {
            As[j] = N - j;
         }
         As[i] = A;
         Bs = new int[N - i - 1];
         int k = 0;
         for (int j = (i == 0) ? N : (As[i - 1] - 1); j > 0 && (k < N - i - 1); j--)
         {
            if (j != As[i])
            {
               Bs[k] = j;
               k++;
            }
         }
         System.out.println(i + 1);
         for (int j = 0; j < i + 1; j++)
         {
            System.out.print(As[j] + " ");
         }
         System.out.println("\n" + (N - i - 1));
         for (int j = 0; j < N - i - 1; j++)
         {
            System.out.print(Bs[j] + " ");
         }
      }
      else
      {
         int i = 0;
         while (B > N - i)
         {
            B -= (N - i);
            i++;
         }
         Bs = new int[i + 1];
         for (int j = 0; j < i; j++)
         {
            Bs[j] = N - j;
         }
         Bs[i] = B;
         As = new int[N - i - 1];
         int k = 0;
         for (int j = (i == 0) ? N : (Bs[i - 1] - 1); j > 0 && (k < N - i - 1); j--)
         {
            if (j != Bs[i])
            {
               As[k] = j;
               k++;
            }
         }
         System.out.println(N - i - 1);
         for (int j = 0; j < N - i - 1; j++)
         {
            System.out.print(As[j] + " ");
         }
         System.out.println("\n" + (i + 1));
         for (int j = 0; j < i + 1; j++)
         {
            System.out.print(Bs[j] + " ");
         }
      }
   }
}
      
      /*int N = scan.nextInt();
      int A[] = new int[N - 1];
      int B[] = new int[N - 1];
      int T[] = new int[N];
      for (int i = 0; i < N - 1; i++)
      {
         A[i] = scan.nextInt();
      }
      for (int i = 0; i < N - 1; i++)
      {
         B[i] = scan.nextInt();
      }
      for (int i = 0; i < N - 1; i++)
      {
         while ((T[i] | T[i + 1]) != A[i] ||
                (T[i] & T[i + 1]) != B[i])
         {
            if (T[i + 1] < 3)
            {
               T[i + 1]++;
            }
            else if (T[i] >= 3)
            {
               if (i != 0)
               {
                  T[i - 1]++;
                  T[i] = 0;
                  T[i + 1] = 0;
                  i -= 2;
                  break;
               }
               System.out.print("NO");
               System.exit(0);
            }
            else
            {
               T[i]++;
               T[i + 1] = 0;
               if (i != 0)
               {
                  i -= 2;
                  break;
               }
            }
         }
      }
      System.out.println("YES");
      for (int i = 0; i < N - 1; i++)
      {
         System.out.print(T[i] + " ");
      }
      System.out.print(T[N - 1]);
   }
}*/