在ACM_DIY群中，有一位叫做“傻崽”的同学由于在数论方面造诣很高，被称为数轮之神！对于任何数论问题，他都能瞬间秒杀！一天他在群里面问了一个神题: 对于给定的3个非负整数 A,B,K 求出满足 (1) X^A = B(mod 2*K + 1) (2) X 在范围[0, 2K] 内的X的个数！自然数论之神是可以瞬间秒杀此题的，那么你呢？

第一行有一个正整数T,表示接下来的数据的组数( T <= 1000) 之后对于每组数据，给出了3个整数A,B,K (1 <= A, B <= 10^9, 1 <= K <= 5 * 10^8)

----------------------------------------------此后一千里---------------------------------------------------------

毒瘤出题人，毁我青春。。。

说正事。。要求模的p并不是一个质数，所以我们先考虑中国剩余定理把它拆开。

我们发现对于每个x^A = B mod pi^ai的解的个数乘起来就是原等式的解的个数，因为拆出的每个方程的解表示原方程的解模拆出的素数幂的值，假设我们拆出了k个方程，那么这k个方程的解和原解又可以建立一个k个方程的方程组，每种不同的方程组都对应原方程一个不同的解，所以原解的个数是拆开后方程解个数的乘积。

然后我们就把问题简化到了x^A = B mod pi^ai的解的个数。

然后大力讨论一波。

如果B mod pi^ai = 0，那么x^A中pi的指数一定要大于等于ai。

如果B 和 pi^ai互质，那么直接把式子取个ln，就变成了Alnx = lnb mod phi(pi^ai)，就是一个扩展欧几里得方程的形式，求下解的个数。

如果B 不满足上面两个条件，就设B = pi^t * b，如果t mod A != 0的话无解，否则原式化为$(\frac{x}{p_i^{\frac{t}{A}}})^A = b\:mod\:p_i^{ai - t}$，就变到了第二种情况，只不过这时取值范围有点小问题，解的数量要乘上$p^{t-\frac{t}{A}}$。

然后ln的求法是bsgs。

代码 ：无