Орак изучает теорию чисел, и его очень заинтересовали свойства делимости.
Для двух натуральных чисел \(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\).
Орак может задавать вам эти вопросы несколько раз.
Примечание
В первом запросе \(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\).