Despojados

Time limit1sMemory limit1024 MB

Summary

Count the divisors of N that are squarefree and have at least two prime factors.

Level: Medium5 of 10
Topics: Number theory, Combinatorics, Math
Solved: No attempts yet

Problem

Every positive integer can be written as a product of prime powers. For example, $252 = 2^2 \times 3^2 \times 7$ .

An integer is despojado if it can be written as a product of two or more distinct primes with no prime used twice. For example, $6 = 2 \times 3$ and $14 = 2 \times 7$ are despojado. On the other hand $28 = 2^2 \times 7$ is not, because the prime $2$ is used twice, and neither $1$ nor $17$ is despojado.

You are given an integer $N$ . Count the divisors of $N$ that are despojado.

Input

The first line contains an integer $N$ ( $1 \le N \le 10^{12}$ ).

Output

Print the number of despojado divisors of $N$ on a single line.

Examples5

Example 1
Input
```
252
```
Expected output
```
4
```
Example 2
Input
```
6469693230
```
Expected output
```
1013
```
Example 3
Input
```
8
```
Expected output
```
0
```
Example 4
Input
```
1
```
Expected output
```
0
```
Example 5
Input
```
88290298627
```
Expected output
```
0
```