Một trong những vấn đề mà nhà toán học Lagrange nghiên cứu là biểu diễn 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 đáp án không giảm khi ~N~ tăng.

Dữ liệu

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

Kết quả

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.

Ví dụ

Sample Input 1

1

Sample Output 1

1

Sample Input 2

3

Sample Output 2

3

Sample Input 3

4

Sample Output 3

3

Sample Input 4

8

Sample Output 4

4

Chấm điểm

• Các test tương ứng với 25% số điểm có ~1 \le N \le 50~

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