import math

T = int(input())

for t in range(0,T) :
    s = input().split()
    n = int(s[0])
    p = int(s[1])

    if p == 1:
        print(0)
        continue
    
    ans = n
    pp = p
    f = -1
    
    while ((math.floor(n / pp) > 0) == True & (pp % p == 0) == True):
        x = (int(math.floor(n / pp)))
        ans = ans + f * x
        f = -f
        pp = pp * p
        #print(ans, end = ' ')
        #print(x, end = ' ')
        #print(pp)
    
    print(ans)
    del ans, n, p, pp, f

用和C++一样的算法却TLE了，奆佬们救救我..