D. Художественное разбиние
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Для двух положительных целых чисел $$$l$$$ и $$$r$$$ ($$$l \le r$$$) обозначим за $$$c(l, r)$$$ количество пар целых чисел $$$(i, j)$$$ таких, что $$$l \le i \le j \le r$$$ и $$$\operatorname{gcd}(i, j) \ge l$$$. Здесь $$$\operatorname{gcd}(i, j)$$$ обозначает наибольший общий делитель (НОД) чисел $$$i$$$ и $$$j$$$.

У вас есть два целых числа $$$n$$$ и $$$k$$$, где $$$1 \le k \le n$$$. Пусть $$$f(n, k)$$$ обозначает минимум $$$\sum\limits_{i=1}^{k}{c(x_i+1,x_{i+1})}$$$ по всем последовательностям из целых чисел $$$0=x_1 \lt x_2 \lt \ldots \lt x_{k} \lt x_{k+1}=n$$$.

Помогите YouKn0wWho найти $$$f(n, k)$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 3 \cdot 10^5$$$)  — количество наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 10^5$$$).

Выходные данные

Для каждого набора входных данных выведите одно целое число — $$$f(n, k)$$$.

Пример
Входные данные
4
6 2
4 4
3 1
10 3
Выходные данные
8
4
6
11
Примечание

В первом наборе входных данных YouKn0wWho может выбрать последовательность $$$[0, 2, 6]$$$. Тогда $$$f(6, 2) = c(1, 2) + c(3, 6) = 3 + 5 = 8$$$, что является минимально возможным.