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$：$1 \cdot 2^2 \cdot 5^1 = 20 = l$
• $k = 2$，$x = 1$，$y = 1$：$2 \cdot 2^1 \cdot 5^1 = 20 = l$
• $k = 4$，$x = 0$，$y = 1$：$4 \cdot 2^0 \cdot 5^1 = 20 = l$
• $k = 5$，$x = 2$，$y = 0$：$5 \cdot 2^2 \cdot 5^0 = 20 = l$
• $k = 10$，$x = 1$，$y = 0$：$10 \cdot 2^1 \cdot 5^0 = 20 = l$
• $k = 20$，$x = 0$，$y = 0$：$20 \cdot 2^0 \cdot 5^0 = 20 = l$

共 6 种不同的 $k$。

---

第二个测试用例：$a = 2, b = 5, l = 21$。
注意到 $l = 21$ 既不能被 $a = 2$ 整除，也不能被 $b = 5$ 整除。因此只能取 $x = 0, y = 0$，对应 $k = 21$。
共 1 种不同的 $k$。

---

第三个测试用例：$a = 4, b = 6, l = 48$。
可能的 $k$ 值（以及对应的 $x, y$）如下：

• $k = 2$，$x = 1$，$y = 1$：$2 \cdot 4^1 \cdot 6^1 = 48 = l$
• $k = 3$，$x = 2$，$y = 0$：$3 \cdot 4^2 \cdot 6^0 = 48 = l$
• $k = 8$，$x = 0$，$y = 1$：$8 \cdot 4^0 \cdot 6^1 = 48 = l$
• $k = 12$，$x = 1$，$y = 0$：$12 \cdot 4^1 \cdot 6^0 = 48 = l$
• $k = 48$，$x = 0$，$y = 0$：$48 \cdot 4^0 \cdot 6^0 = 48 = l$

共 5 种不同的 $k$。