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 (x1, ..., xm), such that

x1 + x2 + ... + xm = x, m is an integer greater than 0, and for each i in {1, ..., m}, xi > 1 and xi is an integer.

 

The desirable formation of x is a formation (x1, ..., xm), in which SUMi in {1, ..., m}bud(xi) is the minimum among all possible formations of x.

The desirable number of x is SUMi in {1, ..., m}bud(xi), such that (x1, ..., xm) 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  107, 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