import Foundation
let q = Int(readLine()!)!
for _ in [Int](repeating: 0, count: q){
    var (t,m) = (-1,0)
    let n = readLine()!.split(separator: " ").map{Int($0)!}
    if n[1] == 1{
        t = n[0] - 1
    }else{
        while n[0] > m{
            t += 1
            m += Int(pow(Double(n[1]),Double(t)))
        }
    }
    print(t)
}