Районная олимпиада по информатике 2017 года за 9 класс | Казахстанские олимпиады

Задача C. Остатки

Даны целые числа $a,$ $b$ и $n.$ Требуется найти количество целых чисел $x$ таких, что $0 \le x < n$ и число $a\cdot x$ при делении на $n$ дает остаток $b.$

Формат входного файла

Единственная строка входного файла содержит три целых числа разделенных пробелом: $a,$ $b$ и $n$ $(0 \le n \le 100000,$ $0 \le a, b < 100000).$

Формат выходного файла

Выведите ответ к задаче.

Примеры

Вход

3 0 6

Выход

3