https://codeforces.com/problemset/problem/1175/A

for avobe problem as editorial the solution is here . but it gives worng answer what is the problem in my python code

for i in range(int(input())): n,m=map(int,input().split()) p=0 while 1: if n%m==0: n/=m n=int(n) p+=1 else: r=(n%m) n-=r p+=r if n==0: break print(p)