package main

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

const MAXN = 100005

var phi [MAXN]int
var S [MAXN]int
var divs [MAXN][]int

func initPrecompute() {
	for i := 0; i < MAXN; i++ {
		phi[i] = i
	}
	for i := 2; i < MAXN; i++ {
		if phi[i] == i {
			for j := i; j < MAXN; j += i {
				phi[j] -= phi[j] / i
			}
		}
	}
	S[0] = 0
	for i := 1; i < MAXN; i++ {
		S[i] = S[i-1] + phi[i]
	}

	for i := 1; i < MAXN; i++ {
		for j := i; j < MAXN; j += i {
			divs[j] = append(divs[j], i)
		}
	}
	for i := 1; i < MAXN; i++ {
		for left, right := 0, len(divs[i])-1; left < right; left, right = left+1, right-1 {
			divs[i][left], divs[i][right] = divs[i][right], divs[i][left]
		}
	}
}

var current_L, current_R, current_cost int

func count_pairs(R, L int) int {
	res := 0
	for _, g := range divs[R] {
		if g < L {
			break
		}
		res += phi[R/g]
	}
	return res
}

func move_to(L, R int) {
	for current_L > L {
		current_L--
		current_cost += S[current_R/current_L]
	}
	for current_R < R {
		current_R++
		current_cost += count_pairs(current_R, current_L)
	}
	for current_L < L {
		current_cost -= S[current_R/current_L]
		current_L++
	}
	for current_R > R {
		current_cost -= count_pairs(current_R, current_L)
		current_R--
	}
}

func getLog2(n int) int {
	res := 0
	for n > 1 {
		n /= 2
		res++
	}
	return res
}

var prevDP [MAXN]int
var currDP [MAXN]int

func main() {
	initPrecompute()

	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	if _, err := fmt.Fscan(reader, &t); err != nil {
		return
	}

	for tc := 0; tc < t; tc++ {
		var n, k int
		fmt.Fscan(reader, &n, &k)

		if k >= getLog2(n)+1 {
			fmt.Fprintln(writer, n)
			continue
		}

		for i := 0; i <= n; i++ {
			prevDP[i] = int(1e18)
		}
		prevDP[0] = 0

		current_L = 1
		current_R = 0
		current_cost = 0

		var compute func(l, r, opt_l, opt_r int)
		compute = func(l, r, opt_l, opt_r int) {
			if l > r {
				return
			}
			mid := (l + r) / 2
			best_cost := int(1e18)
			best_opt := opt_l

			max_j := mid - 1
			if opt_r < max_j {
				max_j = opt_r
			}

			for j := opt_l; j <= max_j; j++ {
				move_to(j+1, mid)
				cost := prevDP[j] + current_cost
				if cost < best_cost {
					best_cost = cost
					best_opt = j
				}
			}

			currDP[mid] = best_cost

			compute(l, mid-1, opt_l, best_opt)
			compute(mid+1, r, best_opt, opt_r)
		}

		for i := 1; i <= k; i++ {
			for j := 0; j <= n; j++ {
				currDP[j] = int(1e18)
			}
			compute(1, n, 0, n-1)
			for j := 0; j <= n; j++ {
				prevDP[j] = currDP[j]
			}
		}

		fmt.Fprintln(writer, prevDP[n])
	}
}