Fibonacci là dãy số kinh điển trong toán học được tìm thấy cách đây hơn 800 năm. Đến nay các nhà khoa học phát hiện nhiều trùng hợp thú vị về dãy số này trong tự nhiên. Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử \(0\) hoặc \(1\) và \(1\), các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Những bài toán về dãy Fibonacci đều khá đa dạng về thể loại và chắc hẳn không còn xa lạ gì đối với chúng ta.

Bài toán hôm nay cũng có thể như vậy: Cho hai số nguyên \(n\), \(M\) và dãy số Fibonacci \(F_1, F_2, \ldots, F_n\) thỏa mãn:

Hãy tìm dãy con không giảm dài nhất của dãy \(F_1, F_2,\ldots, F_n\).

Nhắc lại, một dãy con \(F_{i_1}, F_{i_2}, \ldots, F_{i_k}\) mà trong đó \(1 \leq i_1 < i_2 < \ldots < i_k \leq n\) được gọi là không giảm nếu \(F_{i_1} \leq F_{i_2} \leq \ldots \leq F_{i_k}\).

Input

• Một dòng duy nhất chứa hai số nguyên \(n\) và \(M\) (\(1 \leq n \leq 10^{18}\), \(1 \leq M \leq 10^3\)).

Output

• Một dòng duy nhất chứa một số nguyên là độ dài của dãy con không giảm dài nhất.

Scoring

• Subtask 1 (\(15\%\) số điểm): \(n \leq 10^3\).
• Subtask 2 (\(15\%\) số điểm): \(n \leq 10^6\).
• Subtask 3 (\(20\%\) số điểm): \(M \leq 3\).
• Subtask 4 (\(25\%\) số điểm): \(M \leq 45\).
• Subtask 5 (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

9 5

7