eolymp
bolt
Try our new interface for solving problems
Problems

Кредитная карта

Кредитная карта

Time limit 2 seconds
Memory limit 64 MiB

Победителю индивидуального Кубка Векуа от спонсоров достался крупный денежный приз. Для перечисления этой суммы участник должен назвать номер своей кредитной карты. Проблема в том, что он забыл этот номер, но помнит одно из его свойств: в n-ричной системе счисления это натуральное число состоит из k > 2 попарно различных цифр, при этом если число умножить на 2, то оно будет циклической перестановкой первоначального, то же самое будет, если его умножить на 3... и так далее до k.

Ваша задача - вычислить, сколько таких чисел имеется для заданного n.

Input data

Во входном файле задано единственное число 3n1000 - основание системы счисления.

Output data

Выведите целое число - количество в n-ричной системе счисления чисел с указанным свойством.

Examples

Input example #1
3
Output example #1
0
Source III MSU-CBOSS Open Cup in programming. Grand Prix of South Caucasus, April 29, 2007