艺术分割

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

对于两个正整数 (l,r)（(l\le r)），定义 (c(l,r)) 为满足

[ l\le i\le j\le r,\qquad \gcd(i,j)\ge l ]

的整数对 ((i,j)) 的数量。其中 (\gcd(i,j)) 表示 (i,j) 的最大公约数。

给定两个整数 (n,k)，其中 (1\le k\le n)。对所有满足

[ 0=x_1<x_2<\cdots <x_k<x_{k+1}=n ]

的整数序列，考虑下式：

[ \sum_{i=1}^{k} c(x_i+1,x_{i+1}). ]

请输出这个式子的最小值 (f(n,k))。

输入格式

第一行一个整数 (t)，表示测试用例数。

接下来 (t) 行，每行两个整数 (n,k)，表示一组询问。

输出格式

对每组询问输出一行一个整数 (f(n,k))。

样例输入

4
6 2
4 4
3 1
10 3

样例输出

8
4
6
11

样例解释

对于第一组询问，可以选择序列 ([0,2,6])。此时 (c(1,2)+c(3,6)=3+5=8)，且不存在更优方案。

数据范围

对于所有数据：

• (1\le t\le 300000)；
• (1\le k\le n\le 100000)。