D. Количество пар
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны три положительных (больше нуля) целых числа $$$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$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор состоит из одной строки, содержащей три целых числа $$$c$$$, $$$d$$$ и $$$x$$$ ($$$1 \le c, d, x \le 10^7$$$).

Выходные данные

Для каждого тестового случая выведите одно целое число — количество пар ($$$a, b$$$), таких, что выполняется вышеописанное равенство.

Пример
Входные данные
4
1 1 3
4 2 6
3 3 7
2 7 25
Выходные данные
4
3
0
8
Примечание

В первом примере корректные пары: ($$$1, 4$$$), ($$$4,1$$$), ($$$3, 6$$$), ($$$6, 3$$$).

Во втором примере корректные пары: ($$$1, 2$$$), ($$$2, 1$$$), ($$$3, 3$$$).