package main

import (
	"bufio"
	"fmt"
	"os"
)

func combMin(n, r, cap int64) int64 {
	if r < 0 || r > n || cap <= 0 {
		return 0
	}
	if r > n-r {
		r = n - r
	}
	res := int64(1)
	for i := int64(1); i <= r; i++ {
		a := n - r + i
		res = res * a / i
		if res >= cap {
			return cap
		}
	}
	return res
}

func can(k, n, m int64) bool {
	if n <= 1 {
		return true
	}
	if k == 0 {
		return false
	}
	budget := k * m
	cnt := int64(1)
	ones := int64(0)

	for w := int64(1); w <= k && cnt < n; w++ {
		take := combMin(k, w, n-cnt)
		if take == 0 {
			break
		}
		add := w * take
		if add > budget-ones {
			return false
		}
		ones += add
		cnt += take
	}
	return cnt >= n && ones <= budget
}

func solve(n, m int64) int64 {
	if n == 1 {
		return 0
	}
	lo, hi := int64(0), n-1
	for lo < hi {
		mid := (lo + hi) / 2
		if can(mid, n, m) {
			hi = mid
		} else {
			lo = mid + 1
		}
	}
	return lo
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	var t int
	fmt.Fscan(in, &t)
	for ; t > 0; t-- {
		var n, m int64
		fmt.Fscan(in, &n, &m)
		fmt.Fprintln(out, solve(n, m))
	}
}