题目描述

对于给定的 $3$ 个非负整数 $A,B,k$ 求出满足

• $x^A \equiv B \pmod{2k+1}$

• $x$ 在范围 $[0, 2K]$ 内

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

输入格式

第一行有一个正整数$T$。

对于每组数据，给出了3个整数 $A,B,K$。

输出格式

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

3
213 46290770 80175784
3 46290770 80175784
3333 46290770 80175784

27
27
297

数据范围

$1\le T\le 1000$

$1\le A,B\le 10^9$

$1\le k\le 5\times 10^8$