Giải bài trực tuyến

Lần đầu tiên được tiếp xúc với các vấn đề về cơ sở tin học, các học sinh đều ngỡ ngàng và thú vị khi được làm quan với hệ đếm cơ số 2.

Bài tập về nhà là mỗi người tự chọn cho mình một số nguyên N và viết các số 1, 2, 3, …, N dưới dạng nhị phân. Qua bài tập này, thầy giáo muốn biết:

• Học sinh đã nắm được cách biểu diễn nhị phân hay chưa.
• Đánh giá được mức độ ham mê tin học sinh trong lớp qua số N được chọn và cách trình bày bài làm.

Một bạn đã rất cố gắng thực hiện bài tập, chọn số N khá lớn, ghi các số từ 1 tới N dưới dạng nhị phân, mỗi số trên một dòng. Sau đó để cho bài làm có dạng hấp dẫn hơn, bạn học sinh đó chọn một số nguyên K lớn hớn 0 và ở mỗi dòng – tô đỏ các 0 thứ nhất, thứ K + 1, 2K + 1, … Ở hình trên, N = 56 và K = 2. Các số 0 màu đỏ được gạch dưới.

Các bạn trong lớp rất thích thú khi thấy bài làm này và định in để nộp. Nhưng có một bạn lo lắng: “Máy in màu của mình sắp hết mặc đỏ. Với N và K đã chọn, sẽ có bao nhiêu số 0 được viết bằng màu đỏ?”. Hãy giúp các bạn đang làm bài tập trả lời câu hỏi trên.

Input

Gồm nhiều dòng, mỗi dòng chứa 2 số nguyên N và K cách nhau ít nhất một dấu cách. (1 < N ≤ 2147483647; K > 0)

Output

Gồm nhiều dòng, mỗi dòng gồm 1 số là kết quả tìm được của từng test.

Example

Input:
4 1
56 2

Output:
3
74