491. Game for Little Johnny

Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Most of all in his life John likes his little son Johnny and his favorite integer number N. Well, actually John also likes math, so he wants his son to learn math from the early childhood.

To achieve this goal John plays the following game with Johnny. Each morning he tells the following tale to the son:

"In some magic kingdom there is a very tasty sweet cake and this cake costs exactly N bananas (a monetary unit of this kingdom). However, there are only two types of banknotes in this kingdom, one with the value of A bananas and the other with the value of B bananas (A < B).

According to the kingdom's laws, when buying a product, one has to use the set of banknotes with the total value equal to the product's cost so that no change is required and this set must contain at least one banknote of each of two types. Unfortunately, people in the kingdom are very bad at math, so nobody can find a way to buy the cake. Would you be able to buy it, Johnny?"

In other words, Johnny is given three integers N, A and B, 1 ≤ A < BN, and is required to find integers x, y ≥ 1 such that A· x + B· y = N. If Johnny succeeds at this task, John gives him a real tasty sweet cake as a prize.

For each next day John is going to use different numbers A and B in his tale, but the number N will always be the same (it's his favorite integer after all!). John likes his son, so he wants to always choose A and B in such way that Johnny's task has a solution. And of course John doesn't want to use the same pair (A, B) for two or more different days.

John is worried about the following question: for how long is he able to tell this tale, that is, how many different pairs (A, B) exist such that Johnny's task has a solution? However, John is not so good at math himself (it's a secret, don't tell it to Johnny!), so you have to help him to answer this question.

The input file contains one integer N ().

The output file must contain one integer, the amount of different pairs (A, B) such that Johnny's task has a solution.

sample input
sample output

Note. The pairs from the example test case are (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (2, 3), (2, 4), (2, 6), (2, 8), (3, 4), (3, 7), (4, 6).

Online Contester Team © 2002 - 2010. All rights reserved.