# 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*_{1}*, ..., **x _{m}*), such that

*x _{1} + x_{2} + ... + x_{m} = x*,

*m*is an integer greater than 0, and for each

*i*in

*{1, ..., m}*,

*x*

*> 1 and*

_{i}*x*

*is an integer.*

_{i}

The *desirable* formation of *x* is a formation *(x*_{1}*, ..., **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*

_{1}*, ...,*

*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^{7}, 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 7413Submit

Source: 15th Iran Nationwide Internet Contest