505031 - 数论之王

【题目描述】数论之王(god)

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

Input

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

Output

输出一行表示答案。

Examples

Input

    3
213 46290770 80175784
3 46290770 80175784
3333 46290770 80175784

Output

27
27
297
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题