Với các dòng được đánh số từ ~1~ theo thứ tự từ trên xuống dưới và các cột được đánh số từ ~1~ theo thứ tự từ trái sang phải. Ô thứ ~i, j~ (tức là ô vuông nằm trên giao điểm của dòng thứ ~i~ và cột thứ ~j~) sẽ có giá trị là ~i * j~
Cuối cùng, với tâm hồm và thân xác trẻ con của mình, LK vẽ một con robot xuất phát ở ô ~(1, 1)~ và sẽ đi đến ô lô tô có giá trị là ~N~. Trong mỗi bước đi, con robot của LK chỉ có thể đi đến một trong bốn ô kề cạnh ô mà nó đang đứng. Và LK muốn biết được số bước ít nhất của robot để nó có thể đến ô lô tô có giá trị là ~N~. Nhưng vì còn quá nhỏ nên LK không thực hiện được việc này. Chính vì thế, các bạn hãy giúp đỡ cho bạn nhỏ LK nhóa!!!
(Tất nhiên robot sẽ không được phép đi ra ngoài bảng lô tô)
Input
- Gồm một dòng chứa số nguyên ~N~, là giá trị của ô lô tô mà robot phải đi đến ~(N \le 10^{12})~,
Output
- In ra một số nguyên duy nhất là số bước ít nhất mà robot có thể đi đến các ô có giá trị ~N~
Scoring
- Subtask ~1~ (~50\%~ số điểm): ~N\le 10^3~.
- Subtask ~2~ (~30\%~ số điểm): ~N\le 10^6~.
- Subtask ~3~ (~20\%~ số điểm): ~N\le 10^{12}~
Ví dụ
Input
6
Output
3
Giải thích ví dụ
- Hình minh họa 6 dòng và 6 cột đầu tiên của bảng lô tô.
Ở test ví dụ, con robot cần đi đến ô có giá trị 6. Số bước nhỏ nhất để đi đến ô đó là 3 bước:
1 -> 2 -> 3 -> 6
Bình luận