package main

import . "fmt"

func main() {
	var q int
	Scan(&q)
	for ;q>0;q-- {
		var n,k,c,a int64
		Scan(&n,&k)
		if k==1 {
			Println(n-1)
			continue
		}
		d := 0
		c = 1
		a = 1
		for c < n {
			d++
			a *= k
			c += a
		}
		Println(d)
	}
}