题目描述

有 $q$ 次询问。每次询问给出三个正整数 $c,d,x$，问有多少对正整数 $a,b$ 满足

$$c\times \mathrm{lcm}(a,b)-d\times \gcd(a,b)=x$$

输入格式

第一行一个正整数 $q$，接下来 $q$ 行每行三个正整数 $c,d,x$，表示一次询问。

输出格式

对于每次询问输出一行一个整数表示答案。

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

4
3
0
8

提示

对于 $40\%$ 的数据，$q=1,c,d,x\le 30$。

对于另外 $20\%$ 的数据，$q=1,c,d,x\le 10^4$。

对于另外 $20\%$ 的数据，$q\le 50,c,d,x\le 10^6$。

对于所有数据，$q\le 10^4,c,d,x\le 10^7$。