A. Орак и делители
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Орак изучает теорию чисел, и его очень заинтересовали свойства делимости.

Для двух натуральных чисел $$$a$$$ и $$$b$$$, $$$a$$$ является делителем $$$b$$$ если и только если существует такое натуральное число $$$c$$$, что $$$a\cdot c=b$$$.

Для $$$n \ge 2$$$, обозначим за $$$f(n)$$$ минимальный делитель $$$n$$$, отличный от $$$1$$$.

Например, $$$f(7)=7,f(10)=2,f(35)=5$$$.

Для выбранного числа $$$n$$$ Орак решил прибавить $$$f(n)$$$ к $$$n$$$.

Например, если у него было число $$$n=5$$$, новое значение $$$n$$$ будет равно $$$10$$$. А если у него было число $$$n=6$$$, $$$n$$$ станет равным $$$8$$$.

Ораку так это понравилось, что он решил проделать подобные операции по несколько раз.

Для двух положительных чисел $$$n$$$ и $$$k$$$, Орак попросил вас прибавить $$$f(n)$$$ к $$$n$$$ ровно $$$k$$$ раз (обратите внимание, что $$$n$$$ изменяется после каждой операции, соотвественно $$$f(n)$$$ тоже может измениться) и сказать ему итоговое значение $$$n$$$.

Например, если Орак скажет вам, что $$$n=5$$$ и $$$k=2$$$, сначала вы должны прибавить $$$f(5)=5$$$ к $$$n=5$$$, и новое значение $$$n$$$ станет равным $$$n=10$$$, после этого вы должны прибавить $$$f(10)=2$$$ к $$$10$$$, и новое (и итоговое!) значение $$$n$$$ будет равно $$$12$$$.

Орак может задавать вам эти вопросы несколько раз.

Входные данные

В первой строке записано одно целое число $$$t\ (1\le t\le 100)$$$: количество запросов Орака.

В каждой из следующий $$$t$$$ строк записаны два целых числа $$$n,k\ (2\le n\le 10^6, 1\le k\le 10^9)$$$, описывающие очередной запрос.

Гарантируется, что сумма всех $$$n$$$ не превосходит $$$10^6$$$.

Выходные данные

Выведите $$$t$$$ строк, в $$$i$$$-й из которых должно быть записано итоговое значение $$$n$$$ для $$$i$$$-го запроса Орака.

Пример
Входные данные
3
5 1
8 2
3 4
Выходные данные
10
12
12
Примечание

В первом запросе $$$n=5$$$ и $$$k=1$$$. Делители $$$5$$$ это $$$1$$$ и $$$5$$$, и минимальный делитель, отличный от $$$1$$$ это $$$5$$$. Соответственно, единственная операция это прибавление $$$f(5)=5$$$ к $$$5$$$, поэтому результат равен $$$10$$$.

Во втором запросе $$$n=8$$$ и $$$k=2$$$. Делители $$$8$$$ это $$$1,2,4,8$$$, и минимальный из них кроме $$$1$$$ равен $$$2$$$, затем, после одной операции $$$8$$$ превратится в $$$8+(f(8)=2)=10$$$. Делители $$$10$$$ это $$$1,2,5,10$$$, минимальный делитель, отличный от $$$1$$$ это $$$2$$$, поэтому ответ равен $$$10+(f(10)=2)=12$$$.

В третьем запросе $$$n$$$ изменялось следующим образом: $$$3 \to 6 \to 8 \to 10 \to 12$$$.