package com.codemitts.MayEasyChallenge;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * Created by Sarika on 5/2/2015.
 */
public class SumOfPowers {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            String[] w = br.readLine().split(" ");
            long n = Long.parseLong(w[0]);
            long p = Long.parseLong(w[1]);
            sb.append(digs(n,p)+"\n");
        }
        System.out.print(sb);
    }

    private static long digs(long n, long p) {
        if (p == 1) {
            return n;
        }

        long res = 0;
        while (n > 0) {
            res += n%p;
            n /= p;
        }

        return res;
    }
}
