题目描述

对于给定的 $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$）

输出格式

输出一行，表示答案。

输入输出样例 #1

输入 #1

3
213 46290770 80175784
3 46290770 80175784
3333 46290770 80175784

输出 #1

27
27
297