CDRSANJ - CODER FIRST PROBLEM


Coder Sanjay is now ready to put up his first problem in his favorite website SPOJ. As it is his first problem, he wanted it to be easy so that most of them could get an AC.

The problem statement looks like this:

F(x) is a function whose properties are as follows.

  1. F(x) = 0 at x = 0.
  2. F(x) = 1 at x = 1.
  3. F(x) = 2 at x = 2.
  4. F(x) = 0 if x is an odd prime.
  5. F(a*b) = F(a) + F(b), where a, b are two positive integers and sum of a and b is minimum.

Your task is simple. You are to output the value of F(x) for the given input integer x.

Input

The only line of input contains a single integer x (0 < x < 100001).

Output

Output the value of F(x).

Example

Input:
4

Output:
4

hide comments
Murad Al Wajed: 2016-04-24 08:29:11

nice problem. ac in 1

Shashank Tiwari: 2016-04-16 02:34:59

This is a beautiful problem especially if you try to prove why our method gives minimun answer. You dont have to dig into sieve and store prime numbers . Concentrate on Pattern and above all try to prove things by induction. Your solution should work even if x is 10^19 (Ideally speaking!!).

Last edit: 2016-04-22 16:34:13
utkarsh538: 2016-04-13 22:14:36

easy one,just find the logic. No use of finding prime numbers.

ghost_wire: 2016-03-21 10:17:59

Easy one my 30th problem.

aman anand: 2016-03-16 02:35:37

ac in 1st attempt

Last edit: 2016-03-16 05:22:15
Kyle Dencker: 2016-03-15 03:06:45

Fun good problem.

Last edit: 2016-03-15 04:03:51
lalit_nit: 2016-03-14 15:08:07

Nicely framed!!!!...... 5 mint to get logic

Last edit: 2016-03-14 16:03:48
farhan764: 2016-03-14 11:57:05

in case 5.......concentrate only about 2

vikke: 2016-03-12 22:25:08

nice prob...
easy one..<3
AC in 1 go...

sri: 2016-03-12 15:55:45

try this testcases
input : 6 9 100 120 100000
output: 2 0 4 6 10
try with all the approaches


Added by:verdu sanjay
Date:2016-03-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU