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. ≥0) integers k, x, and y such that l=k⋅ax⋅by.
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≤t≤104) — the number of test cases.
The following t lines contain three integers, a, b and l (2≤a,b≤100, 1≤l≤106) — description of a test case.
Output t lines, with the i-th (1≤i≤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 |
---|