Ngày 2/9, Phúc quyết định bao cả đội tuyển ra Hà Nội chơi lễ. Có ~n~ thành phố đánh số từ ~1~ tới ~n~, trong đó:

• Thành phố ~1~ là nơi đội tuyển đang ở.
• Thành phố ~n~ là Hà Nội.

Các thành phố nằm trên một tuyến đường thẳng. Từ thành phố ~i~, bạn có thể đi thẳng tới thành phố ~j~ (~j > i~) nếu và chỉ nếu khoảng cách ~j - i~ chia hết cho 2 hoặc chia hết cho 9 (gợi nhớ ngày 2/9).

Chi phí di chuyển giữa ~i~ và ~j~ = ~(j - i)^2~ (bình phương khoảng cách).

Yêu cầu: Hãy giúp Phúc tìm chi phí nhỏ nhất để đưa cả đội từ thành phố ~1~ đến thành phố ~n~. Nếu không thể đi được, in ~-1~.

Dữ liệu vào

• Một số nguyên dương ~n~ (~2 \le n \le 2 \cdot 10^5~) — số thành phố.

Dữ liệu ra

• In ra chi phí nhỏ nhất để đi từ thành phố ~1~ đến thành phố ~n~, hoặc ~-1~ nếu không thể.

Ràng buộc

• Subtask 1 ~(30\%)~: ~2 \le n \le 2000~
• Subtask 2 ~(30\%)~: ~2 \le n \le 5 \times 10^4~
• Subtask 3 ~(40\%)~: Không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vào

20

Kết quả ra

101

Giải thích Đường đi tương ứng:

1 → 10 (bước 9) : chi phí 81

10 → 12 (bước 2) : chi phí 4

12 → 14 (bước 2) : chi phí 4

14 → 16 (bước 2) : chi phí 4

16 → 18 (bước 2) : chi phí 4

18 → 20 (bước 2) : chi phí 4

Tổng = 81+4+4+4+4+4 =101