# [Solution] Artistic Partition solution codeforces

## Artistic Partition solution codeforces

For two positive integers 𝑙l and 𝑟r (𝑙𝑟l≤r) let 𝑐(𝑙,𝑟)c(l,r) denote the number of integer pairs (𝑖,𝑗)(i,j) such that 𝑙𝑖𝑗𝑟l≤i≤j≤r and gcd(𝑖,𝑗)𝑙gcd⁡(i,j)≥l. Here, gcd(𝑖,𝑗)gcd⁡(i,j) greatest common divisor (GCD) of integers 𝑖i and 𝑗j.

YouKn0wWho has two integers 𝑛n and 𝑘k where 1𝑘𝑛1≤k≤n. Let 𝑓(𝑛,𝑘)f(n,k) denote the minimum of 𝑖=1𝑘𝑐(𝑥𝑖+1,𝑥𝑖+1)∑i=1kc(xi+1,xi+1) over all integer sequences 0=𝑥1<𝑥2<<𝑥𝑘<𝑥𝑘+1=𝑛0=x1<x2<…<xk<xk+1=n.

## Artistic Partition solution codeforces

Input

The first line contains a single integer 𝑡t (1𝑡31051≤t≤3⋅105) — the number of test cases.

The first and only line of each test case contains two integers 𝑛n and 𝑘k (1𝑘𝑛1051≤k≤n≤105).

## Artistic Partition solution codeforces

Output

For each test case, print a single integer — 𝑓(𝑛,𝑘)f(n,k).

## Artistic Partition solution codeforces

Example
input

Copy
4
6 2
4 4
3 1
10 3


## Artistic Partition solution codeforces

output

Copy
8
4
6
11


## Artistic Partition solution codeforces

Note

In the first test case, YouKn0wWho can select the sequence [0,2,6][0,2,6]. So 𝑓(6,2)=𝑐(1,2)+𝑐(3,6)=3+5=8f(6,2)=c(1,2)+c(3,6)=3+5=8 which is the minimum possible.