P12694 BZOJ2219 数论之神

对于给定的 $3$ 个非负整数 $A,B,K$，求出满足： - $X^A \equiv B \pmod{(2\times K + 1)}$ - $X$ 在范围 $[0, 2K]$ 内 的 $X$ 的个数。

第一行有一个正整数 $T$，表示接下来的数据的组数（$T \leq 1000$）。之后对于每组数据，给出了 $3$ 个整数 $A, B, K$ （$1 \leq A, B \leq 10^9$, $1 \leq K \leq 5 \times 10^8$）

输出一行，表示答案。