题目描述

定义 $f(n)$ 为 $n$ 的最小非平凡因子，也就是除了 $1$ 之外的最小因子（本题不讨论非正数因子）

给出两个正整数 $n,k$，你需要进行 $k$ 次操作，每次将 $n$ 加上 $f(n)$（注意这里 $n$ 在每次操作后是会变化的）

输入格式

本题有多组数据

第一行一个整数 $T$，表示数据组数

接下来 $T$ 行，每行两个整数 $n,k$，表示一组数据

输出格式

对于每组数据，输出一行一个整数，表示 $k$ 次操作后的 $n$

说明/提示

$1 \le T \le 100$ $1 \le n \le 10^6$，$1 \le k \le 10^9$ $\sum n \le 10^6$

感谢 @_Wolverine 提供的翻译

样例

3
5 1
8 2
3 4

10
12
12