### 问题描述

小明和小红是一对恋人，他们相爱已经三年了，在今年的七夕节，小明准备给小红一个特殊的礼物。他想要送给小红一些数字，让小红算出有多少对正整数 $(a,b)$ 满足以下条件： $$c \times lcm(a,b) - d \times gcd(a,b) = x$$ 其中 $c, d, x$ 是小明给出的数字，$gcd(a,b)$ 为 $a,b$ 的最大公因数，$lcm(a,b)$ 为 $a,b$ 的最小公倍数 。

小明希望这个问题能够考察小红对于数论基础知识的理解和运用，同时也希望小红能够在这个特殊的日子里感受到他对她的深情。请你帮助小明实现他的想法吧！

输入格式

第一行包含一个正整数 $T$（$1\leq T \leq 10^3$），表示询问的组数。

接下来 $T$ 行，每行包含三个正整数 $c, d, x$（$1\leq c,d,x \leq 10^5$）。

输出格式

对于每组询问，输出一个正整数表示满足条件的 $(a,b)$ 对数。

样例输入

2
2 3 6
4 5 7

样例输出

4
2