Author: | Антон Карабанов | Time limit: | 2 sec | |
Input file: | Standard input | Memory limit: | 512 Mb | |
Output file: | Standard output |
Two students are preparing for exam, when they will get a single question out of n possible ones. They decided to split questions to study as follows:
First student picks a number a from 1 to n and learns a questions numbered a, a + 1, a + 2, ... , a + a − 1. If some number exceeds n, numbering continues from 1. For example, if n = 5 and a = 1, the first student will only learn question 1, when a = 2 he will learn questions 2 and 3, when a = 4 — questions 4, 5, 1 and 2, when a = 5 — all questions.
Second student also picks a number b ≠ a from 1 to n and learns b questions numbered b, b + 1, b + 2, ... , b + b − 1. Similarly, if some number exceeds n, numbering continues from 1.
Given number of questions n determine number of different ways to choose a and b, such that every question will be learned by at least one of students.
Input contains an integer n.
Output an integer — number of ways to choose a and b.
2 ≤ n ≤ 106
In the first sample all possible choices of a и b result in learning all questions.
In the second sample there are four questions. If a = 1, and b = 2, question number 4 will not be learned by either student.
If a = 1, and b = 3, question number 2 will not be learned by either student.
In other cases all questions will be studied.
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|