505031 - 数论之王

【题目描述】数论之王（god）

做为数论之王的你，需要帮助你的朋友解决这个问题，即对于给定的3个非负整数A，B，K，求出满足：(1) XA = B(mod 2K+1)；(2) X在范围[0，2K]内的X的个数。

第一行有一个正整数T，表示接下来的数据的组数( T≤1000) ，之后对于每组数据，给出了3个整数A，B，K (1≤A，B≤10^9，1≤K≤5╳10^8)

输出一行表示答案。