Once upon a time, there was a curious mathematician named Alice. She loved playing with numbers. One day, she encountered a challenge. In this challenge, she had to assume that a magical box containing numbers from \(1\) to \(N\) existed, and she had to select \(M\) distinct numbers from this box such that the sum of their divisors was the greatest, and then report this maximum possible sum of their divisors.

Alice had to solve this puzzle multiple times for various values of \(N\) and \(M\) since she was quite busy she asked for your help.

The rules of the challenge are:

You have to answer \(T\) such puzzles.
For each puzzle, you are provided with two integers, \(N\) and \(M\).
Your task is to determine the maximum total sum of the divisors of \(M\) distinct numbers from \(1\) to \(N\).

Input format

The first line contains a single integer \(T\), which denotes the number of puzzles.
Each of the next \(T\) lines contains two integers \(N\) and \(M\).

Output format

For each puzzle, print in a new line the maximum total sum of the divisors of \(M\) distinct numbers from \(1\) to \(N\).

Constraints

\(1 \leq T \leq 10^6 \\ 1 \leq M ≤ N \leq 2×10^6\)