```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	fmt.Fscan(reader, &t)

	for ; t > 0; t-- {
		var n, k int
		fmt.Fscan(reader, &n, &k)

		if n%2 == 0 {
			fmt.Fprintln(writer, n+2*k)
		} else {
			d := n
			for i := 3; i*i <= n; i += 2 {
				if n%i == 0 {
					d = i
					break
				}
			}
			fmt.Fprintln(writer, n+d+2*(k-1))
		}
	}
}
```