SP8074 NUMG - God of Number Theory

在 ACM\_DIY 俱乐部中，有一位被称为「ShaZai」的高手。大家都知道，他是处理「数论」问题的专家，总能在瞬间解决这些问题！然而，对我们来说，这些问题完全是无从下手。有一天，ShaZai 给我们出了一道题： 现在，给你三个非负整数 $A$、$B$ 和 $K$。请你计算出多少个整数 $X$ 满足以下条件： 1. $X^A \equiv B \pmod{2K + 1}$ 2. $X$ 的取值范围是 $[0, 2K]$ 我们被这个问题难住了，能请你帮我们解决吗？

第一行输入一个整数 $T$，表示测试用例的数量。（$T \leq 1000$） 接下来的每一行包含三个整数 $A$、$B$ 和 $K$。（$1 \leq A, B \leq 10^9$，$1 \leq K \leq 5 \times 10^8$）

对于每个测试用例，输出满足条件的 $X$ 的数量。 **本翻译由 AI 自动生成**