给定三个正整数 $x,y,k$ , 求满足 $x \times lcm(a,b) - y \times gcd(a,b) = k$ 的数对 $(a,b)$ 的数量 ，其中 $lcm(a,b)$ 是 $a,b$ 的最小公倍数 ， $gcd(a,b)$ 是 $a,b$ 的最大公约数。

若 $a \neq b$ 那么 $(a,b)$ 与 $(b,a)$ 是两个不同的数对。

输入格式

第一行一个整数 $t$ , 表示数据组数。$(1 \leq t \leq 10^3)$

接下来 $t$ 行，每行输入三个整数 $x,y,k$ , 含义如题面所示。 $( 1 \leq x,y,k \leq 10^7 )$。

输出格式

输出 $t$ 行，每行一个整数，表示满足要求二元对的数量。

样例输入

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

样例输出

4
3
0
8