With university applications around the corner, James decides to apply for the University of Watermoo. However, in order to do that, he needs to get "gud" and do well on the Euclid Math contest hosted by said university. Thus he decides to not repeat the same mistake this year and actually study for the Euclid contest. In particular, he is currently studying primes. He knows the math but he wants to check his work. So he hires you, a slave friend to create a program that would answer his questions.

His questions are in the following form:

• Let ~F(x, k)~ be defined as the ~k^\text{th}~ smallest prime greater than or equal to ~x~. If ~x~ is prime, then ~F(x, 1) = x~. Given two positive integers ~x~ and ~k~, James wants to know ~F(x, k)~. He also wants to know the sum of all primes from ~x~ to ~F(x, k)~ inclusive.

Since James really wants to test his skills, he will ask your program ~Q~ times.

Note: Fast I/O is recommended for this problem. For this problem, Python users are recommended to use PyPy over CPython.

Constraints

For all subtasks:

~1 \le x \le 100\,000~

~1 \le k \le 10\,000~

~1 \le Q \le 500\,000~

Subtask 1 [20%]

~1 \le x \le 1\,000~

~1 \le k \le 100~

~Q \le 1\,000~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain one integer ~Q~, denoting the number of questions your program has to answer.

The next ~Q~ lines will contain the two integers ~x, k~.

Output Specification

Output ~Q~ lines. On each line, output two space-separated integers. ~F(x, k)~ and the sum of all primes from ~x~ to ~F(x, k)~ inclusive.

Sample Input

4
1 5
2 6
11 1
14 4

Sample Output

11 28
13 41
11 11
29 88

Explanation for Sample Output

For the first question, ~F(1, 5) = 11~. The sum of all the primes in ~[1, 11]~ is ~2+3+5+7+11 = 28~.

For the second question, ~F(2, 6) = 13~. The sum of all the primes in ~[2, 13]~ is ~2+3+5+7+11+13 = 41~.

For the third question, ~F(11, 1) = 11~. The sum of all the primes in ~[11, 11]~ is ~11~.

For the last question, ~F(14, 4) = 29~. The sum of all the primes in ~[14, 29]~ is ~17+19+23+29 = 88~.