Thảo là một người có đam mê về toán học, anh ấy thích các tính chất của số học đặc biệt là ước số. Ngoài ra anh ấy có tính cách vui nhộn là thích thử thách người khác, vì vậy anh ấy có một vấn đề đặc biệt đưa ra để bạn giải quyết như sau:

Có hai số nguyên ~a~ và ~b~, ~a~ là ước của ~b~ khi và chỉ khi tồn tại một số nguyên ~c~ sao cho ~a * c = b~ . Cho ~2 \le n~, ~f(n)~ là ước nhỏ nhất của ~n~ khác ~1~

Ví dụ: ~f(7) = 7, f(10) = 2, f(35) = 5~

Thấy bài toán còn quá đơn giản bạn Thảo quyết định tăng độ khó bài toán bằng cách thêm ~f(n)~ vào ~n~. Ví dụ với ~n = 5~ kết quả mới của ~n~ sẽ là ~10~ ~(5 + f(5))~; ~n = 6~ kết quả sẽ là ~8~ ~(6 + f(6)~. Cảm thấy thú vị nên anh ấy quyết định lặp lại thao tác này nhiều lần.

Bây giờ, bạn được cho hai số nguyên ~n~ và ~k~, anh ấy yêu cầu bạn thêm ~f(n)~ vào ~n~ chính xác ~k~ lần (lưu ý ~n~ sẽ thay đổi sau mỗi lần lặp, ~f(n)~ cũng sẽ thay đổi theo). Hãy trả lời cho Thảo đại ca nghe về kết quả cuối cùng của ~n~ để nhận được những phần quà đặc biệt.

Input

• Một dòng gồm 2 số nguyên ~n (2 \le n \le 10^6)~ và ~k (1 \le k \le 10^9)~,

Output

• Kết quả cuối cùng của ~n~

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

8 2

Output

12

Giải thích ví dụ

• Giải thích: 8 có các ước ~1, 2, 4, 8~, ước nhỏ nhất khác ~1~ là ~2~. Sau đó ~n = 8 + (f(8) = 2) = 10~

Tiếp theo ~10 + (f(10) = 2) = 12~