C. Количество значений k
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны три положительных целых числа $$$a$$$, $$$b$$$ и $$$l$$$ ($$$a,b,l>0$$$).

Можно показать, что всегда существует способ выбрать неотрицательные (т.е. $$$\ge 0$$$) целые числа $$$k$$$, $$$x$$$ и $$$y$$$ таким образом, что $$$l = k \cdot a^x \cdot b^y$$$.

Ваша задача — найти количество различных возможных значений $$$k$$$ для всех таких способов.

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

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

Следующие $$$t$$$ строк содержат три целых числа, $$$a$$$, $$$b$$$ и $$$l$$$ ($$$2 \le a, b \le 100$$$, $$$1 \le l \le 10^6$$$) — описание набора входных данных.

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

Выведите $$$t$$$ строк, где $$$i$$$-я ($$$1 \le i \le t$$$) строка содержит целое число — ответ на $$$i$$$-й набор входных данных.

Пример
Входные данные
11
2 5 20
2 5 21
4 6 48
2 3 72
3 5 75
2 2 1024
3 7 83349
100 100 1000000
7 3 2
2 6 6
17 3 632043
Выходные данные
6
1
5
12
6
11
24
4
1
3
24
Примечание

В первом наборе входных данных примера $$$a=2, b=5, l=20$$$. Возможные значения $$$k$$$ (и соответствующие $$$x,y$$$) следующие:

  • Выберите $$$k = 1, x = 2, y = 1$$$. Тогда $$$k \cdot a^x \cdot b^y = 1 \cdot 2^2 \cdot 5^1 = 20 = l$$$.
  • Выберите $$$k = 2, x = 1, y = 1$$$. Тогда $$$k \cdot a^x \cdot b^y = 2 \cdot 2^1 \cdot 5^1 = 20 = l$$$.
  • Выберите $$$k = 4, x = 0, y = 1$$$. Тогда $$$k \cdot a^x \cdot b^y = 4 \cdot 2^0 \cdot 5^1 = 20 = l$$$.
  • Выберите $$$k = 5, x = 2, y = 0$$$. Тогда $$$k \cdot a^x \cdot b^y = 5 \cdot 2^2 \cdot 5^0 = 20 = l$$$.
  • Выберите $$$k = 10, x = 1, y = 0$$$. Тогда $$$k \cdot a^x \cdot b^y = 10 \cdot 2^1 \cdot 5^0 = 20 = l$$$.
  • Выберите $$$k = 20, x = 0, y = 0$$$. Тогда $$$k \cdot a^x \cdot b^y = 20 \cdot 2^0 \cdot 5^0 = 20 = l$$$.

Во втором наборе входных данных примера $$$a=2, b=5, l=21$$$. Обратите внимание, что $$$l = 21$$$ не делится ни на $$$a = 2$$$, ни на $$$b = 5$$$. Поэтому мы можем установить только $$$x = 0, y = 0$$$, что соответствует $$$k = 21$$$.

В третьем наборе входных данных примера $$$a=4, b=6, l=48$$$. Возможные значения $$$k$$$ (и соответствующие $$$x,y$$$) следующие:

  • Выберите $$$k = 2, x = 1, y = 1$$$. Тогда $$$k \cdot a^x \cdot b^y = 2 \cdot 4^1 \cdot 6^1 = 48 = l$$$.
  • Выберите $$$k = 3, x = 2, y = 0$$$. Тогда $$$k \cdot a^x \cdot b^y = 3 \cdot 4^2 \cdot 6^0 = 48 = l$$$.
  • Выберите $$$k = 8, x = 0, y = 1$$$. Тогда $$$k \cdot a^x \cdot b^y = 8 \cdot 4^0 \cdot 6^1 = 48 = l$$$.
  • Выберите $$$k = 12, x = 1, y = 0$$$. Тогда $$$k \cdot a^x \cdot b^y = 12 \cdot 4^1 \cdot 6^0 = 48 = l$$$.
  • Выберите $$$k = 48, x = 0, y = 0$$$. Тогда $$$k \cdot a^x \cdot b^y = 48 \cdot 4^0 \cdot 6^0 = 48 = l$$$.