Distinct Prime Divisors

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Count distinct prime divisors of positive integer n, counting each prime only once. For n=1 output zero.

Input

One positive integer n.

Output

One integer: number of distinct prime factors.

Subtasks

• Subtask 1 (20%): n ≤ 1000.

• Subtask 2 (30%): n ≤ 10^8.

• Subtask 3 (50%): n ≤ 10^12.

Examples

Example 1

Input:

72

Output:

2

Explanation: 72 has distinct prime divisors 2 and 3.

Example 2

Input:

1

Output:

0

Explanation: One has no prime divisors.

Example 3

Input:

97

Output:

1

Explanation: 97 has one prime divisor, itself.