Một ông chủ khó tính, muốn các nhân viên xếp các hộp hàng hình lập phương thành những đống hàng có 1 trong 2 dạng: (1) hình lập phương (2) hình kim tự tháp. Ví dụ: nếu có 38 thùng hàng thì chỉ cần xếp thành 2 đống hàng: 1 đống lập phương cạnh là 2 (8 thùng hàng) và 1 kim tự tháp cao là 4 (30 thùng hàng = \(1^2 + 2^2 + 3^2 + 4^2\)).

Hình minh họa cách xếp đống hàng vừa ý ông chủ:

Input Có nhiều bộ test.

• Mỗi bộ test là số lượng thùng hàng hình lập phương trên 1 dòng.
• Input kết thúc khi gặp \(-1\).

Output

• Với mỗi bộ test, ouput ra số lượng đống hàng ít nhất thỏa yêu cầu của ông chủ khó tính.

Input mẫu

38
60
12
39101
-1

Output mẫu

2
2
4
4