题目描述

给定三个正整数 $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$ 行输出第 $i$ 个测试用例的答案，即不同 $k$ 的取值个数。

说明/提示

在第一个测试用例中，$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$。

由 ChatGPT 4.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