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?

Input

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

Output

In ra một số nguyên duy nhất là đáp án của câu hỏi.

Simple Input 1

1

Simple Output 1

1

Simple Input 2

3

Simple Output 2

3

Simple Input 3

8

Simple Output 3

4