Для двух положительных целых чисел \(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)\).
В первом наборе входных данных YouKn0wWho может выбрать последовательность \([0, 2, 6]\). Тогда \(f(6, 2) = c(1, 2) + c(3, 6) = 3 + 5 = 8\), что является минимально возможным.
4 6 2 4 4 3 1 10 3
8 4 6 11
3000 ms 1024 Mb Правила оформления программ и список ошибок при автоматической проверке задач