from collections import deque
def naive(x,y,a):
  if x==y:
    return 0
  todo=deque()
  todo.append((x,0))
  seen=set([x])
  while todo:
    v,res=todo.popleft()
    if v==y:
      return res
    if res>10:
      return 10**9
    if v+1 not in seen:
      seen.add(v+1)
      todo.append((v+1,res+1))
    if v>0 and v-1 not in seen:
      seen.add(v-1)
      todo.append((v-1,res+1))
    if v*a not in seen:
      seen.add(v*a)
      todo.append((v*a,res+1))
    if v//a not in seen:
      seen.add(v//a)
      todo.append((v//a,res+1))


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

memo={}

def calc(y,x,a,k):
  if y in memo:
    return memo[y]
  ans=abs(y-x)
  tmpL,tmpR=y,y+1
  res=0
  while tmpR//a<=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=min(abs(y1*a-y)+1,abs(y-y1))+calc(y1,x,a,k+1)
    ans=min(ans,res1)
  y2=(y+a-1)//a
  if y2<y:
    res2=min(abs(y2*a-y)+1,abs(y-y2))+calc(y2,x,a,k+1)
    ans=min(ans,res2)
  
  if k<=120:
    ans=min(ans,calc(y+1,x,a,k+1)+1)
    if y!=0:
      ans=min(ans,calc(y-1,x,a,k+1)+1)
  memo[y]=ans
  return ans

for _ in range(0):
  import random
  memo.clear()
  x=random.randint(0,10**18)
  y=random.randint(0,10**18)
  a=random.randint(2,10**18)
  print(calc(y,x,a,1))

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