数论之神

在 ACM_DIY 群中，有一位叫做「傻崽」的同学由于在数论方面造诣很高，被称为数论之神！对于任何数论问题，他都能瞬间秒杀。

一天他在群里面问了一个神题：对于给定的 $3$ 个非负整数 $A, B, K$，求出满足

$$X^A\equiv B\pmod{2K+1},\qquad 0\le X\le 2K$$

的 $X$ 的个数。

自然，数论之神是可以瞬间秒杀此题的，那么你呢？

输入格式

第一行有一个正整数 $T$，表示接下来的数据的组数。

之后每组数据一行，给出 $3$ 个整数 $A, B, K$。

输出格式

对于每组数据，输出一行一个整数表示答案。

样例输入

3
213 46290770 80175784
3 46290770 80175784
3333 46290770 80175784

样例输出

27
27
297

数据范围

• $T\le 1000$；
• $1\le A\le 10^9$，$1\le B\le 10^9$；
• $1\le K\le 5\times 10^8$。

来源与许可

本题题面与测试数据整理自 BZOJ 2219。

样例 1

输入

3
213 46290770 80175784
3 46290770 80175784
3333 46290770 80175784

输出

27
27
297