Một trong những vấn đề mà nhà toán học Lagrange nghiên cứu là vấn đề chia một số nguyên dương thành tổng bình phương của các số nguyên sao cho số bình phương được sử dụng là ít nhất. Ví dụ:

• 3 = 1^2 + 1^2 + 1^2 (sử dụng 3 bình phương)
• 4 = 2^2 (sử dụng 1 bình phương). Có cách chia 4 = 1^2 + 1^2 + 1^2 + 1^2, tuy nhiên cách chia này sử dụng 4 bình phương và không phải là cách chia sử dụng số lượng bình phương ít nhất.
• 5 = 2^2 + 1^2 (sử dụng 2 bình phương)

Lagrange đã chứng minh được rằng:

• Mọi số nguyên dương đều có thể được biểu diễn bằng tổng bình phương của 4 số nguyên.
• Cho một số nguyên dương N, hãy viết chương trình trả lời câu hỏi: Để phân chia một số nguyên dương bất kì không vượt quá N sao cho số bình phương được sử dụng ít nhất, ta cần nhiều nhất bao nhiêu bình phương?

Lưu ý rằng khi số N được cho càng lớn, đáp án cho câu hỏi này sẽ càng lớn.

Gồm một dòng duy nhất chứa một số nguyên dương N (1 \leq N \leq 10^8).

Gồm một dòng duy nhất chứa một số nguyên dương là đáp án của câu hỏi.

Subtask:

• Các test tương ứng với 25% số điểm có 1 \leq n \leq 50
• Các test còn lại tương ứng với 75% số điểm có 1 \leq n \leq 10^8