Người ta nói không ai giàu ba họ, không ai khó ba đời. Nhưng năm nay, CLB H3.2 có một team ICPC không những chăm chỉ mà cả ba đều rất giàu mạnh, nghe đến tên thành viên thôi là đủ biết điều đó: Phú, Tài và Lộc. Ngoài những cuộc thi, họ còn đầu tư tài chính nhiều nơi và thu về được một khoản tiền lớn. Để dễ tích lũy, Tài đã đề xuất rằng nên chia nó thành các rương tiền rồi cất vào tủ sách của H3.2. Lộc đồng ý, nhưng muốn rằng số tiền trong mỗi rương phải là số đẹp, tức là lũy thừa bậc ~k>1~ của một số nguyên dương nào đó (số mũ này không nhất thiết giống nhau ở tất cả các rương tiền); ngoài ra, Lộc cũng đã mã hóa số tiền lại, chỉ giữ lại số mũ của chúng. Cuối cùng, Phú được giao nhiệm vụ lưu giữ các số mũ đó, và vì không muốn tính toán nhiều, bạn muốn tổng các số đó là nhỏ nhất có thể. Hãy giúp team tính ra giá trị đó nhé.

Input:

Số nguyên dương ~n~ với ~1 \le n \le 10^5~ cho biết số tiền của team (đơn vị tiền là đô la).

Output:

Tổng nhỏ nhất có thể có.

Sample input 1:

1

Sample output 1:

2

Sample input 2:

21

Sample output 2:

6

Sample input 3:

57

Sample output 3:

5

Giải thích: ta thấy rằng ~1 = 1^2~ nên team sẽ lưu lại số ~2~, còn ~21=1^2+2^2+4^2~ nên team sẽ lưu lại ~2+2+2=6;~ trong VD cuối, ta có ~57=49+8=7^2+2^3~ nên kết quả là ~2+3=5.~