数论之神

时间限制:3s      空间限制:259MB

题目描述

在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)


输出格式

输出一行,表示答案


样例输入

3
213 46290770 80175784
3 46290770 80175784
3333 46290770 80175784


样例输出

27
27
297

提示

 新加数组一组--2015.02.27


题目来源

数论 鸣谢 AekdyCoin