D :: The Masochist

Time Limit: 3 Seconds    Memory Limit: 32768 KB

For an integer x, bud(x) is defined to be the largest divisor of x other than x itself.

A formation of a given number x is a sequence (x₁, ..., x_m), such that

x₁ + x₂ + ... + x_m = x, m is an integer greater than 0, and for each i in {1, ..., m}, x_i > 1 and x_i is an integer.

 

The desirable formation of x is a formation (x₁, ..., x_m), in which SUM_{i in {1, ..., m}}bud(x_i) is the minimum among all possible formations of x.

The desirable number of x is SUM_{i in {1, ..., m}}bud(x_i), such that (x₁, ..., x_m) is the desirable formation of x. 

The desirable number of a set of numbers is defined as the summation of the desirable numbers of its elements.

 

Given two integer numbers N and K find a subset of size K from {y | 2 ≤ y ≤ N} that has the smallest desirable number. 

Input

The first line of the input contains a single integer T (1 ≤ T ≤ 50), which is the number of test cases.

Each of the following T lines contains two space-separated integers N and K (2 ≤ N ≤ 10⁷, 1 ≤ K ≤ N-1).

Output

 For each test case print a single number in a separate line.

It represents the minimum desirable number among all subsets of size K of {y | 2 ≤ y \≤ N}.

Sample Input

3
10 5
100 15
9999 4321

Sample Output

6
15
7413

Submit

Source: 15th Iran Nationwide Internet Contest