Codeforces Round 929 (Div. 3) |
---|
Finished |
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.
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 $$$t$$$ lines, with the $$$i$$$-th ($$$1 \le i \le t$$$) line containing an integer, the answer to the $$$i$$$-th test case.
112 5 202 5 214 6 482 3 723 5 752 2 10243 7 83349100 100 10000007 3 22 6 617 3 632043
6 1 5 12 6 11 24 4 1 3 24
In the first test case, $$$a=2, b=5, l=20$$$. The possible values of $$$k$$$ (and corresponding $$$x,y$$$) are as follows:
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:
Name |
---|