题目描述

有$\red{t}$组询问，给定三个整数$\red{c,d,x，}$问有多少对正整数对$\red{(a,b)}$使得$\red{c\times lcm(a,b)-d\times gcd(a,b)=x}$。

输入格式

第一行一个整数$\red{t，}$表示数据组数。

对于每组数据，一行三个整数$\red{c,d,x，}$表示输入。

输出格式

对于每组数据，一行一个整数，表示答案。

样例

输入样例

4
1 1 3
4 2 6
3 3 7
2 7 25

输出样例

4
3
0
8

提示

对于$\red{50\%}$的数据，$\red{1<=c,d,x<=10^3}$。

对于$\red{100\%}$的数据，$\red{1<=t<=10^4,1<=c,d,x<=10^7}$。