Вам даны три положительных (больше нуля) целых числа \(c\), \(d\) и \(x\).
Вы должны найти количество пар положительных целых чисел \((a, b)\) таких, что выполняется равенство \(c \cdot lcm(a, b) - d \cdot gcd(a, b) = x\). Где \(lcm(a, b)\) — наименьшее общее кратное \(a\) и \(b\), а \(gcd(a, b)\) — наибольший общий делитель \(a\) и \(b\).
Выходные данные
Для каждого тестового случая выведите одно целое число — количество пар (\(a, b\)), таких, что выполняется вышеописанное равенство.
Примечание
В первом примере корректные пары: (\(1, 4\)), (\(4,1\)), (\(3, 6\)), (\(6, 3\)).
Во втором примере корректные пары: (\(1, 2\)), (\(2, 1\)), (\(3, 3\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1 3
4 2 6
3 3 7
2 7 25
|
4
3
0
8
|