Khang có vô số hình vuông kích thước \(1 \cdot 1\) chưa tô màu. Cho số nguyên dương \(n\) (\(2 \le n \le 10^{15}\)). Khang lần lượt sắp các hình vuông kích thước \(1 \cdot 1\) theo quy tắc sau:

• Hàng \(1\): có \(1\) ô vuông.
• Hàng \(2\): có \(2\) ô vuông.
• Hàng \(3\): có \(3\) ô vuông.
• ...
• Hàng thứ \(n\): có \(n\) ô vuông.

Khang lần lượt chọn các hình vuông có kích thước lớn hơn hoặc bằng \(2 \cdot 2\) trong một tam giác vuông cân chưa tô màu để tô màu vàng và phải đảm bảo quy tắc: các ô vuông kích thước \(1 \cdot 1\) chưa tô màu phải thuộc về một tam giác vuông cân có cạnh vuông lớn hơn hoặc bằng \(2\) (cụ thể: các ô vuông chưa tô màu tạo thành các tam giác vuông cân phân biệt có cạnh vuông \(\ge 2\)).

Ví dụ với \(n=4\):

Các ô vuông (\(1 \cdot 1\)) chưa tô màu đảm bảo thuộc về một tam giác vuông cân có cạnh vuông \(\ge 2\). Các bạn hãy giúp Khang tô màu tối ưu sao cho số lượng ô vuông kích thước (\(1 \cdot 1\)) chưa tô màu là tối thiểu (các ô vuông này phải thỏa mãn nằm trong một tam giác vuông cân có cạnh vuông \(\ge 2\) và chỉ chứa các ô chưa tô màu).

Input

• Một số nguyên dương \(n\) (\(2 \le n \le 10^{15}\)).

Output

• In ra một số duy nhất là số lượng hình vuông kích thước \(1 \cdot 1\) chưa được tô màu tối thiểu tìm được.

Example

4

6

Scoring

• Subtask \(1\) (\(80\%\) số điểm): \(2 \le n < 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(2 \le n \le 10^{15}\).