The Bytelandian cryptographer acknowledged he was sorely beaten in Act 2. He renounced his own methods of encryption and decided to return to the classic techniques.

Not knowing what to do next, he went to the cinema to chew the problem over. To his surprise, he found that the cone containing pop-corn was in fact a rolled up page torn from the classic book, RSA for newbies in 24 seconds. The page in question contained the entire key-generating and encryption algorithm. Fascinated, he thought up two different prime numbers p and q, and calculated his own public key, and revealed the product p*q to the wide world. Then, he began work on his wicked scheme of encryption.

History repeats. Once more, you receive an encrypted message from the cryptographer. This time you know that without additional information you are beaten, so you decide to use the psychological approach. You phone the Bytelandian cryptographer, and ask him whether he couldn't give you a little hint. What you really want to know is the number u of positive integers which are smaller than pq and have no common factors with pq other than 1. But the cryptographer, sensing that this would allow you to decode the message right away, refuses to tell you this number. Eventually, after a lot of asking, he gives you a piece of utterly useless information: he tells you how many positive integers x cannot be represented in the form x=ap+bq, regardless of what non-negative integer values a and b assume.

You begin to wonder whether the information you received from the cryptographer is not by any chance enough to find the value of u. Even if the only languages at your disposal are Brainf**k and Intercal...

Input

The number provided by the cryptographer (a positive integer of at most 99 decimal digits). The input ends with a new line symbol.

Output

The value of u.

Example

Input:

1

Output:

2

(This example is possible for p=2, q=3)