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)

输出

输出一行表示答案。

样例

输入

    3
213 46290770 80175784
3 46290770 80175784
3333 46290770 80175784

输出

27
27
297
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题