Tổng các bình phương (Squares)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Với số nguyên dương $N$, hãy biểu diễn $N$ thành tổng các bình phương của các số nguyên và tìm số lượng số hạng nhỏ nhất.

Input

Dòng duy nhất chứa $N$.

Output

In số lượng bình phương ít nhất cần dùng.

Subtask

• Subtask 1 — 20 điểm: 1 <= N <= 30. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: 1 <= N <= 2500. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 1 <= N <= 10000. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

50

Output

2

Giải thích

$50=5^2+5^2$, nên cần 2 số hạng; 50 không phải là một số chính phương.