Вам даны три положительных целых числа \(a\), \(b\) и \(l\) (\(a,b,l>0\)).
Можно показать, что всегда существует способ выбрать неотрицательные (т.е. \(\ge 0\)) целые числа \(k\), \(x\) и \(y\) таким образом, что \(l = k \cdot a^x \cdot b^y\).
Ваша задача — найти количество различных возможных значений \(k\) для всех таких способов.
Выходные данные
Выведите \(t\) строк, где \(i\)-я (\(1 \le i \le t\)) строка содержит целое число — ответ на \(i\)-й набор входных данных.
Примечание
В первом наборе входных данных примера \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|