Breaking the Superconductor

You developed a room-temperature, ambient-pressure superconductor and wrote a paper that will change the world. You have a block of superconductor weighing $N\mathrm{g}$. To verify the paper, $K$ laboratories have asked for superconductor samples. Each laboratory needs a sample of at least $1\mathrm{g}$. Fortunately, you have a technique for breaking superconductors precisely. For an integer $a$ with $2 \le a$, a piece of $a\mathrm{g}$ can be cut as follows.

• Choose an integer $b$ with $1 \le b < a$.
• Split the piece into one piece of $b\mathrm{g}$ and one piece of $(a-b)\mathrm{g}$.
• The cut costs $a$ won.

To reduce research costs, you need to find the minimum cost of cutting the superconductor into $K$ pieces. You can assume that under the constraints, the superconductor can be split into $K$ pieces using the method above.

The first line contains the number of test cases $T$.

Each of the next $T$ lines contains two integers $N$ and $K$, separated by a space. $N$ is the weight of the superconductor block, and $K$ is the number of laboratories that asked for samples.

For each test case, print the minimum cost of cutting the superconductor into $K$ pieces.

• $1 \le T \le 100\,000$
• $2 \le K \le N \le 1\,000\,000\,000$
• All given numbers are integers.