311095: CF1933C. Turtle Fingers: Count the Values of k

C. Turtle Fingers: Count the Values of ktime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given three positive integers $a$, $b$ and $l$ ($a,b,l>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.

Input

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.

Output

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

ExampleInput

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

Output

6
1
5
12
6
11
24
4
1
3
24

Note

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、b和l（a、b、l>0），存在非负整数k、x和y，使得l=k*a^x*b^y。任务是找出所有这样的方式中k的不同可能值的数量。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
接下来的t行，每行包含三个整数a、b和l（2≤a,b≤100，1≤l≤10^6）——一个测试用例的描述。

输出数据格式：
输出t行，第i行（1≤i≤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*a^x*b^y=1*2^2*5^1=20=l。
- 选择k=2, x=1, y=1，则k*a^x*b^y=2*2^1*5^1=20=l。
- 选择k=4, x=0, y=1，则k*a^x*b^y=4*2^0*5^1=20=l。
- 选择k=5, x=2, y=0，则k*a^x*b^y=5*2^2*5^0=20=l。
- 选择k=10, x=1, y=0，则k*a^x*b^y=10*2^1*5^0=20=l。
- 选择k=20, x=0, y=0，则k*a^x*b^y=20*2^0*5^0=20=l。

在第二个测试用例中，a=2, b=5, l=21。注意，l=21不能被a=2或b=5整除。因此，我们只能设置x=0, y=0，对应k=21。题目大意： 给定三个正整数a、b和l（a、b、l>0），存在非负整数k、x和y，使得l=k*a^x*b^y。任务是找出所有这样的方式中k的不同可能值的数量。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 接下来的t行，每行包含三个整数a、b和l（2≤a,b≤100，1≤l≤10^6）——一个测试用例的描述。 输出数据格式： 输出t行，第i行（1≤i≤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*a^x*b^y=1*2^2*5^1=20=l。 - 选择k=2, x=1, y=1，则k*a^x*b^y=2*2^1*5^1=20=l。 - 选择k=4, x=0, y=1，则k*a^x*b^y=4*2^0*5^1=20=l。 - 选择k=5, x=2, y=0，则k*a^x*b^y=5*2^2*5^0=20=l。 - 选择k=10, x=1, y=0，则k*a^x*b^y=10*2^1*5^0=20=l。 - 选择k=20, x=0, y=0，则k*a^x*b^y=20*2^0*5^0=20=l。 在第二个测试用例中，a=2, b=5, l=21。注意，l=21不能被a=2或b=5整除。因此，我们只能设置x=0, y=0，对应k=21。