A positive integer is sphenic if it is the product of exactly three distinct primes. Determine whether \(N\) is sphenic.

Input

One line containing \(N\).

The input satisfies:

• \(1 \le N \le 10^18\)

Output

Print 1 if \(N\) is sphenic; otherwise, print 0.

Example

Input

1

Output

0