SP8074 NUMG - God of Number Theory

In ACM\_DIY, there is one master called “ShaZai”. As we know, he is the god of “Number Theory”. He always kills the problem about “Number Theory” in seconds! But of course we do not have any idea about these problems~ One day in ACM\_DIY, ShaZai asks us one problem: You are given three non-negative integers A, B and K, you are expected to find the number of number that satisfy (1) X^A = B( mod (2K + 1) ) (2) X is in the ranger \[0, 2K\]; Of course we have no idea about this problem, so could you help us?

The first line is one integer T indicates the number of the test cases. (T

Output the answer in a single line.