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

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

Для n≥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.

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