Cho một số nguyên dương ~N~. Ta gọi một số nguyên dương ~k~ là hợp lệ nếu tồn tại hai số nguyên dương ~a~ và ~b~ sao cho ~N = a^k \times b^k~. Nói cách khác, ~N~ có thể được biểu diễn dưới dạng ~N = (a \times b)^k~ với ~a, b \ge 1~.

Yêu cầu

Hãy tìm giá trị lớn nhất của ~k~ sao cho ~N~ có thể biểu diễn dưới dạng trên.

Input

Đọc từ tệp NUMBER.INP chứa duy nhất số nguyên dương ~N~.

Output

Ghi vào tệp NUMBER.OUT một số nguyên dương là giá trị lớn nhất của ~k~ thỏa mãn yêu cầu bài toán.

Ví dụ

Input

216

Output

3

Giải thích: ~216 = (2 \times 3)^3~, giá trị lớn nhất tìm được là ~3~.

Giới hạn

• Có 40% số test của bài thỏa mãn ~N \le 10^3~.
• Có 40% số test tiếp theo của bài thỏa mãn ~10^3 < N \le 10^6~.
• Có 20% số test còn lại của bài thỏa mãn ~10^6 < N \le 10^{12}~.