Maximum Effective Operations

Given a positive integer \(n\). In each operation, you can choose two primes \(y\) and \(z\), where \(z\) is an odd prime. Let \(x=y^{z}\). If \(x\) divides \(n\) completely (i.e. \(n \bmod x = 0\)), it counts as an effective operation, and \(n\) is updated to \(\frac{n}{x}\).

Determine the maximum number of effective operations that can be performed on \(n\).

Note: The optimal strategy is to choose the smallest possible odd prime for \(z\), which is \(3\). Therefore, if the prime factorization of \(n\) is \(n=\prod_{i} p_i^{e_i}\), the answer is \(\sum_{i}\left\lfloor\frac{e_i}{3}\right\rfloor\).

Constraints: \(1 \le n \le 10^{12}\).

inputFormat

The input consists of a single integer \(n\).

outputFormat

Output a single integer representing the maximum number of effective operations that can be performed on \(n\).

sample

1

0