CF1933C.Turtle Fingers: Count the Values of k

You are given three positive integers $a$, $b$ and $l$ ($a,b,l \gt 0$).

It can be shown that there always exists a way to choose non-negative (i.e. $\ge 0$) integers $k$, $x$, and $y$ such that $l = k \cdot a^x \cdot b^y$.

Your task is to find the number of distinct possible values of $k$ across all such ways.

给你三个正整数 $a$、$b$ 和 $l$（即 $a,b,l \gt 0$）。

可以证明：总存在非负整数（即 $\ge 0$）$k$、$x$ 和 $y$，使得 $l = k \cdot a^x \cdot b^y$ 成立。

你的任务是：求出所有满足该等式的方案中，$k$ 的不同可能取值的个数。

The first line contains the integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The following $t$ lines contain three integers, $a$, $b$ and $l$ ($2 \le a, b \le 100$, $1 \le l \le 10^6$) — description of a test case.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

接下来的 $t$ 行每行包含三个整数 $a$、$b$ 和 $l$（$2 \le a, b \le 100$，$1 \le l \le 10^6$）—— 表示一个测试用例的描述。

Output $t$ lines, with the $i$-th ($1 \le i \le t$) line containing an integer, the answer to the $i$-th test case.

输出 $t$ 行，其中第 $i$ 行（$1 \le i \le t$）包含一个整数，表示第 $i$ 个测试用例的答案。

In the first test case, $a=2, b=5, l=20$. The possible values of $k$ (and corresponding $x,y$) are as follows:

• Choose $k = 1, x = 2, y = 1$. Then $k \cdot a^x \cdot b^y = 1 \cdot 2^2 \cdot 5^1 = 20 = l$.
• Choose $k = 2, x = 1, y = 1$. Then $k \cdot a^x \cdot b^y = 2 \cdot 2^1 \cdot 5^1 = 20 = l$.
• Choose $k = 4, x = 0, y = 1$. Then $k \cdot a^x \cdot b^y = 4 \cdot 2^0 \cdot 5^1 = 20 = l$.
• Choose $k = 5, x = 2, y = 0$. Then $k \cdot a^x \cdot b^y = 5 \cdot 2^2 \cdot 5^0 = 20 = l$.
• Choose $k = 10, x = 1, y = 0$. Then $k \cdot a^x \cdot b^y = 10 \cdot 2^1 \cdot 5^0 = 20 = l$.
• Choose $k = 20, x = 0, y = 0$. Then $k \cdot a^x \cdot b^y = 20 \cdot 2^0 \cdot 5^0 = 20 = l$.

In the second test case, $a=2, b=5, l=21$. Note that $l = 21$ is not divisible by either $a = 2$ or $b = 5$. Therefore, we can only set $x = 0, y = 0$, which corresponds to $k = 21$.

In the third test case, $a=4, b=6, l=48$. The possible values of $k$ (and corresponding $x,y$) are as follows:

• Choose $k = 2, x = 1, y = 1$. Then $k \cdot a^x \cdot b^y = 2 \cdot 4^1 \cdot 6^1 = 48 = l$.
• Choose $k = 3, x = 2, y = 0$. Then $k \cdot a^x \cdot b^y = 3 \cdot 4^2 \cdot 6^0 = 48 = l$.
• Choose $k = 8, x = 0, y = 1$. Then $k \cdot a^x \cdot b^y = 8 \cdot 4^0 \cdot 6^1 = 48 = l$.
• Choose $k = 12, x = 1, y = 0$. Then $k \cdot a^x \cdot b^y = 12 \cdot 4^1 \cdot 6^0 = 48 = l$.
• Choose $k = 48, x = 0, y = 0$. Then $k \cdot a^x \cdot b^y = 48 \cdot 4^0 \cdot 6^0 = 48 = l$.

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