from sys import stdin
input=lambda :stdin.readline()[:-1]

memo={}

def calc(y,x,a):
  if y==0:
    return x
  if y in memo:
    return memo[y]
  ans=abs(y-x)
  tmpL,tmpR=y,y+1
  res=0
  while tmpL<x:
    tmpL*=a
    tmpR*=a
    res+=1
    if tmpL<=x<tmpR:
      ans=min(ans,res)
    else:
      ans=min(ans,res+min(abs(tmpL-x),res+abs(tmpR-x)))
  
  y1=y//a
  if y1<y:
    res1=abs(y1*a-y)+calc(y1,x,a)+1
    ans=min(ans,res1)
  y2=(y+a-1)//a
  if y2<y:
    res2=abs(y2*a-y)+calc(y2,x,a)+1
    ans=min(ans,res2)
  memo[y]=ans
  return ans

for _ in range(int(input())):
  memo.clear()
  x,y,a=map(int,input().split())
  print(calc(y,x,a))