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.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Contest {

    //private static List<Integer> results = new ArrayList<>();
    //private static Map<Integer, List<Integer>> map = new HashMap<>();
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        //String line = "100000";

        long n = Long.valueOf(line);

        for (int i = 0; i < n; i++) {
            line = sc.nextLine();
            String[] split = line.split(" ");
            
            long result = getMinimum(Long.valueOf(split[0]), Long.valueOf(split[1]));
            System.out.println(result);
        }
        return;
        //done();
    }

    private static long getMinimum(long n, long k) {
        long counter = 0;
        while (n != 0) {
            long division = n % k;
            if (division == 0) {
                n = n / k;
                counter++;
            } else {
                n -= division;
                counter += division;
            }
        }
        return counter;
    }

    public static boolean isPrime(int num) {
        if (num > 2 && num % 2 == 0) {
            //System.out.println(num + " is not prime");
            return false;
        }
        int top = (int) Math.sqrt(num) + 1;
        for (int i = 3; i < top; i += 2) {
            if (num % i == 0) {
                //System.out.println(num + " is not prime");
                return false;
            }
        }
        //System.out.println(num + " is prime");
        return true;
    }

    public static boolean CheckPrime(int numberToCheck) {
        int remainder;
        for (int i = 2; i <= numberToCheck / 2; i++) {
            remainder = numberToCheck % i;
            if (remainder == 0) {
                return false;
            }
        }
        return true;

    }

    private static void doneList(List<Integer> a) {
        StringBuilder builder = new StringBuilder("");
        for (int i = 0; i < a.size(); i++) {
            builder.append(a.get(i)).append(" ");
        }
        System.out.println(builder.toString().substring(0, builder.toString().length() - 1));
    }

    private static void doneArray(Integer[] a) {
        StringBuilder builder = new StringBuilder("");
        for (int i = 2; i < a.length; i++) {
            builder.append(a[i]).append(" ");
        }
        System.out.println(builder.toString().substring(0, builder.toString().length() - 1));
    }

    private static void done() {
        System.out.println("-1");
    }

    private static int lowerBound(int[] a, int low, int high, int element) {
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (element > a[middle]) {
                low = middle + 1;
            } else {
                high = middle;
            }
        }
        return low;
    }

    private static int upperBound(int[] a, int low, int high, int element) {
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (a[middle] > element) {
                high = middle;
            } else {
                low = middle + 1;
            }
        }
        return low;
    }

}
