Số chính phương là số có thể viết dưới dạng bình phương của một số tự nhiên.

Ví dụ: ~1, 4, 49~ là các số chính phương còn ~2, 5, 20~ không phải là số chính phương.

Hôm nay, thầy giáo cho Minh bài toán sau:

Cho số tự nhiên ~n~, sau đó phân tích ~n = k_1 + k_2 + k_3 + k_4 + \ldots~ Trong đó, các giá trị ~k_1, k_2, k_3, k_4, \ldots~ được tìm theo quy tắc:

• Tìm số chính phương ~k_1~ lớn nhất không vượt quá ~n~.
• Tiếp theo, thực hiện tương tự bước trên với ~n = n - k_1~ để tìm ~k_2~.
• Để tìm ~k_3, k_4, \ldots~ thực hiện tương tự như trên cho đến khi ~n = 0~.

Yêu cầu

Hãy tính giá trị của ~S = (k_1)^1 + (k_2)^2 + (k_3)^3 + (k_4)^4 + \ldots~

Theo em, giá trị của ~S~ là bao nhiêu?

Dữ liệu vào

Gồm một số nguyên dương ~n~ ~(1 \le n \le 10^{14})~.

Kết quả

Gồm một số nguyên duy nhất là giá trị ~S~ tìm được.

Ràng buộc dữ liệu

• Có 60% test có ~1 \le n \le 10^6~.
• Có 40% test có ~10^6 < n \le 10^{14}~.

Ví dụ

Ví dụ 1

INPUT

30

OUTPUT

42

Giải thích: Với ~n = 30~, ta có ~n = 25 + 4 + 1~ nên ~S = 25^1 + 4^2 + 1^3 = 42~.

Ví dụ 2

INPUT

25

OUTPUT

25

Giải thích: Với ~n = 25~, nên ~S = 25^1 = 25~.