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
dawnwillcome: 2022-07-16 06:36:53

AC in one go~

piyush_raz: 2021-09-27 14:34:31

only observation is required

rky673: 2020-06-29 16:17:30

Omg!!!!! I kept thinking for long, getting runtime errors while running locally only to find out how easy it was.

black_shroud: 2020-06-16 10:02:41

i used sieve in o(nlogn) what is the complexity for recursion???

jagdeep_one7: 2020-05-22 07:11:07

good use of recursion

sudipandatta: 2020-02-05 00:26:40

easiest question on spoj

sunny_chand: 2019-02-26 14:18:37

don't forget that in f(a*b)=f(a)+f(b) ,f(a) and f(b)can further be individually expressed as f(x)+f(y) where x*y=a

kushagra_2: 2018-12-15 08:14:42

observe the pattern and you'll get it!!!

pranjal1_: 2018-06-27 09:40:16

don't be discouraged ,if you are not able to solve it ,try,try,and keep on trying .
It will be done ,just think simple

rajcoolaryan: 2018-06-18 09:22:24

f(2) important hai..


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