Tổng bình phương.

Mọi số nguyên dương N đều có thể phân tích thành tổng các bình phương của các số nhỏ hơn N. Ví dụ số 100 = 10^2 hoặc 100 = 5^2 + 5^2 + 5^2 + 5^2. Cho số nguyên dương N. Nhiệm vụ của bạn là tìm số lượng ít nhất các số nhỏ hơn N mà có tổng bình phương bằng N.

Input Format

Một số tự nhiên N được viết trên 1 dòng.(1≤N≤10000)

Constraints

.

Output Format

Đưa ra kết quả của bài toán.

Ví dụ:

Dữ liệu vào

100

Dữ liệu ra

1