import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

immutable int INF = 1 << 29;

void main() {
    auto T = readln.chomp.to!int;
    while (T--) {
        auto s = readln.split.map!(to!long);
        auto N = s[0];
        auto K = s[1];
        long cnt = 0;
        while (N > 0) {
            long m = N % K;
            if (m == 0) {
                N /= K;
                cnt += 1;
            } else {
                N -= m;
                cnt += m;
            }
        }
        cnt.writeln;
    }
}

