Phiên bản này khác phiên bản (A) ở chỗ là team giàu có hơn, với tổng tài sản lên đến hàng tỷ.

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 ~10^5 < n \le 10^{10}~ 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:

100000000

Sample output 1:

2

Sample input 2:

1000000007

Sample output 2:

7

Giải thích: trong VD1, ta thấy số đã cho là ~10000^2~, còn trong VD2, ta có thể biểu diễn: ~1723^2 + 37^3 + 31575^2 = 10^9+7~ nên kết quả là ~2+2+3=7.~