Задача L. Learning distribution

Автор:Антон Карабанов   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Два студента готовятся к экзамену, во время которого им будет предложен один из n вопросов (нумерация от 1 до n). Они решили разделить между собой вопросы для подготовки следующим образом:

Первый студент выбирает одно число a от 1 до n и учит a вопросов с номерами a, a + 1, a + 2, ... , a + a − 1. Если какой-то из номеров превышает n, нумерация продолжается с 1. Например, если n = 5 и a = 1, то первый студент будет учить только вопрос с номером 1, при a = 2 он будет учить вопросы с номерами 2 и 3, при a = 4 — вопросы с номерами 4, 5, 1 и 2, при a = 5 — все вопросы.

Второй студент тоже выбирает одно число b ≠ a от 1 до n и учит b вопросов с номерами b, b + 1, b + 2, ... , b + b − 1. Аналогично, если какой-то из номеров превышает n, счет продолжается с номер 1.

По известному количеству билетов n определите, сколько существует различных способов выбрать a и b, так что каждый вопросы экзамена будет подготовлен хотя бы одним из студентов.

Формат входных данных

Входные данные содержат целое число n.

Формат выходных данных

Выведите целое число — количество способов выбрать a и b.

Ограничения

2 ≤ n ≤ 106

Пояснение к примерам

В первом примере на экзамене три билета. Независимо от выбора a и b, студенты подготовятся к ответам на все вопросы.

Во втором примере на экзамене четыре билета. Если один из студентов выберет a = 1, а другой b = 2, ни один из них не подготовит ответ на четвертый вопрос.

Если один из студентов выберет a = 1, а другой b = 3, ни один из них не подготовит ответ на второй вопрос.

В оставшихся случаях все вопросы будут выучены.

Примеры тестов

Стандартный вход Стандартный выход
1
3
6
2
4
8

0.113s 0.016s 15