module Main where

import Control.Monad (forM_)

main :: IO ()
main = do
  q <- readLn
  forM_ [0..q-1] $ \_ -> do
    [n, k] <- getIntegerList
    print $ solve n k

solve :: Integer -> Integer -> Integer
solve n 1 = n - 1
solve n k = let go :: Integer -> Integer -> Integer -> Integer
                go acc x cnt | acc >= n  = cnt
                             | otherwise = go (acc + x) (x * k) $ cnt + 1
            in  go 1 k 0
 
getIntegerList :: IO [Integer]
getIntegerList = map read . words <$> getLine