B'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 <= t <= 10^4 ) -- the number of test cases. The following t lines contain three integers, a , b and l ( 2 <= a, b <= 100 , 1 <= l <= 10^6 ) -- 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. 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: '...