Cuộc bầu cử tổng thống tại một quốc đảo có đúng hai ứng cử viên: Sam và Bob. Bầu cử được tổ chức theo cơ chế phân cấp gồm ~k~ vòng.

• Ở vòng ~1~, toàn bộ ~n~ cử tri được chia thành các khu vực bầu cử mức ~1~, mỗi khu vực có số cử tri bằng nhau, và mỗi khu vực bầu ra đúng một đại cử tri.
• Sang vòng ~2~, các đại cử tri của vòng ~1~ lại được chia thành các khu vực mức ~2~, mỗi khu vực có số đại cử tri bằng nhau, rồi mỗi khu vực bầu ra một đại cử tri cho vòng tiếp theo.
• Quá trình tiếp tục như vậy cho đến hết vòng ~k~ (sau vòng ~k~ chỉ còn đúng ~1~ người chiến thắng cuối cùng).

Trong mỗi khu vực ở bất kỳ vòng nào:

• Ứng cử viên nào có số phiếu nhiều hơn sẽ thắng, và đại cử tri của khu vực sẽ bỏ phiếu cho người đó ở vòng sau.
• Nếu số phiếu bằng nhau, theo luật bầu cử thì Sam thắng (do là đương kim tổng thống).

Thăm dò cho thấy ban đầu mọi cử tri đều sẽ bầu cho Bob. Tiểu ban của Sam có thể mua chuộc một số cử tri bằng cách tặng mỗi người 1 máy lọc nước; khi đó cử tri đó sẽ bầu cho Sam.

Giả sử tiểu ban của Sam được phép tự chọn cách chia nhóm ở mỗi vòng, miễn là trong cùng một vòng mọi khu vực có kích thước bằng nhau. Hãy tính số máy lọc nước ít nhất cần tặng để đảm bảo Sam thắng chung cuộc.

Yêu cầu

Cho ~n~ và ~k~, hãy tìm số nguyên nhỏ nhất ~x~ sao cho có thể:

• Chọn một cách phân chia người tham gia ở từng vòng thành các khu vực có kích thước bằng nhau,
• Mua chuộc đúng ~x~ cử tri ở vòng ~1~ (mỗi cử tri được tặng 1 máy lọc),
• Để sau ~k~ vòng bầu cử, Sam là người thắng cuối cùng.

Dữ liệu

Gồm một dòng chứa hai số nguyên ~n~ và ~k~.

Kết quả

In ra một số nguyên: số máy lọc nước tối thiểu cần tặng.

Ví dụ

Ví dụ 1

Input

9 2

Output

4

Ví dụ 2

Input

12 3

Output

2

Ràng buộc và chấm điểm

• ~1 \le n \le 10^{15}~
• ~1 \le k \le 10~