Squares

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

For a positive integer $N$, represent $N$ as a sum of integer squares and find the minimum possible number of terms.

Input

The only line contains $N$.

Output

Print the minimum number of square terms.

Subtasks

• Subtask 1 — 20 points: 1 <= N <= 30.
• Subtask 2 — 30 points: 1 <= N <= 2500.
• Subtask 3 — 50 points: 1 <= N <= 10000.

Examples

Input

50

Output

2

Explanation

$50=5^2+5^2$, so 2 terms are enough, and 50 is not itself a perfect square.