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.

/*
9 2
        1 1 1 1 1 0 0 0 0
        1 2
        1 5
        5 6
        5 7
        2 3
        2 4
        3 8
        3 9
*/




import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Question{


    static LinkedList<Integer> adj[] ;
    static boolean[] visited;
    static boolean[] visited_;
    static int[] ans;
    static int count_ = 0;
    static final int MAX_SIZE = 1000001;
    static Vector<Boolean>isprime = new Vector<>(MAX_SIZE);
    static Vector<Integer>prime = new Vector<>();
    static Vector<Integer>SPF = new Vector<>(MAX_SIZE);
    public static  void main(String[] args) throws IOException {
        Reader.init(System.in);
        int q = Reader.nextInt();
        while (q-->0){
            long n = Reader.nextLong();
            long k = Reader.nextLong();
            long cnt = 0;
            while (n!=0){
                if (n%k==0){
                    n = n/k;
                    cnt++;
                }
                else{
                    cnt+=(n%k);
                    n = n-(n%k);

                }
                //System.out.println(n + " " + cnt);

            }
            System.out.println(cnt);
        }





















}
    static void manipulated_seive(int N)
    {
        // 0 and 1 are not prime
        isprime.set(0, false);
        isprime.set(1, false);

        // Fill rest of the entries
        for (int i=2; i<N ; i++)
        {
            // If isPrime[i] == True then i is
            // prime number
            if (isprime.get(i))
            {
                // put i into prime[] vector
                prime.add(i);

                // A prime number is its own smallest
                // prime factor
                SPF.set(i,i);
            }

            // Remove all multiples of  i*prime[j] which are
            // not prime by making isPrime[i*prime[j]] = false
            // and put smallest prime factor of i*Prime[j] as prime[j]
            // [for exp :let  i = 5, j = 0, prime[j] = 2 [ i*prime[j] = 10]
            // so smallest prime factor of '10' is '2' that is prime[j] ]
            // this loop run only one time for number which are not prime
            for (int j=0;
                 j < prime.size() &&
                         i*prime.get(j) < N && prime.get(j) <= SPF.get(i);
                 j++)
            {
                isprime.set(i*prime.get(j),false);

                // put smallest prime factor of i*prime[j]
                SPF.set(i*prime.get(j),prime.get(j)) ;
            }
        }
    }
    static int countGreater(long arr[], int n, long k)
    {
        int l = 0;
        int r = n - 1;

        // Stores the index of the left most element
        // from the array which is greater than k
        int leftGreater = n;

        // Finds number of elements greater than k
        while (l <= r) {
            int m = l + (r - l) / 2;

            // If mid element is greater than
            // k update leftGreater and r
            if (arr[m] > k) {
                leftGreater = m;
                r = m - 1;
            }

            // If mid element is less than
            // or equal to k update l
            else
                l = m + 1;
        }

        // Return the count of elements greater than k
        return (n - leftGreater);
    }

    static void sortbyColumn(int arr[][], int col)
    {
        // Using built-in sort function Arrays.sort
        Arrays.sort(arr, new Comparator<int[]>() {

            @Override
            // Compare values according to columns
            public int compare(final int[] entry1,
                               final int[] entry2) {

                // To sort in descending order revert
                // the '>' Operator
                if (entry1[col] > entry2[col])
                    return 1;
                else
                    return -1;
            }
        });  // End of function call sort().
    }
    static int binarySearchCount(long arr[], int n, long key,int left)
    {
        int right = n;

        int mid = 0;
        while (left < right) {
            mid = (right + left) >> 1;

            // Check if key is present in array
            if (arr[mid] == key) {

                // If duplicates are present it returns
                // the position of last element
                while (mid+1<n && arr[mid + 1] == key)
                    mid++;
                break;
            }

            // If key is smaller, ignore right half
            else if (arr[mid] > key)
                right = mid;

                // If key is greater, ignore left half
            else
                left = mid + 1;
        }

        // If key is not found in array then it will be
        // before mid
        while (mid > - 1 && arr[mid] > key)
            mid--;

        // Return mid + 1 because of 0-based indexing
        // of array
        return mid + 1;
    }

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

    }

    // method to return LCM of two numbers
    static long lcm(long a, long b)
    {
        return (a*b)/gcd(a, b);
    }

    static long fun(long n){
        long max = -1;
        for (int i = 0 ; i < n ; i++){
            String x = Integer.toString(i);
            long product = 1;
            for (int j = 0 ; j < x.length() ; j++){
                product = product * Long.parseLong(Character.toString(x.charAt(j)));
            }
            max = Math.max(product,max);
        }
        return max;
    }

    public static void print2D(int mat[][])
    {
        // Loop through all rows
        for (int[] row : mat)

            // converting each row as string
            // and then printing in a separate line
            System.out.println(Arrays.toString(row));
    }




}



class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}

class MergeSort {
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(int arr[], int l, int m, int r) {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int[n1];
        int R[] = new int[n2];

        /*Copy data to temp arrays*/
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    void sort(int arr[], int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = (l + r) / 2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    static long phi(long n,long R)
    {

        long result = R;


        for (long p = 2; p * p <= n; ++p)
        {


            if (n % p == 0)
            {


                while (n % p == 0)
                    n =n/p;
                result =result - ( result / p);
            }
        }


        //System.out.println("n" + n);
        if (n > 1)
            result -= result / n;
        return result;
    }
}

class person{
    int index;
    int money;

    public person(int index, int money) {
        this.index = index;
        this.money = money;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public void setMoney(int money) {
        this.money = money;
    }

    public int getIndex() {
        return index;
    }

    public int getMoney() {
        return money;
    }
}

class StudentComparator implements Comparator<person>{

    // Overriding compare()method of Comparator
    // for descending order of cgpa
    public int compare(person s1, person s2) {
        if (s1.money > s2.money)
            return 1;
        else if (s1.money < s2.money) {
            return -1;
        }
        else{
            if (s1.index >s2.index){
                return 1;
            }
            else{
                return -1;
            }
        }

    }
}

