9040: Cirno's Perfect Equation Class

Ran is a puzzle lover and loves solving all kinds of math puzzles. One day, Cirno gives her an easy equation: ka+b=cka+b=cka+b=c.
Cirno gives the value of $k$, $c$ and $n$, and want to know how many positive integer pairs $(a,b)$ satisfy ka+b=cka+b=cka+b=c, $b|c$ (that means $c=xb$, $x\ge 1$ and $x$ is an integer) and $\gcd (a,b)\ge n$.
Cirno will ask $q$ questions (that means there'll be $q$ data cases). Help Ran answer them!

The first line contains on integer $q$ (1≤q≤1001\le q\le 1001≤q≤100), means the number of test cases.
For the next $q$ lines, each line contains three integers k,c,nk,c,nk,c,n (1≤k,c,n≤1091\le k,c,n\le 10^91≤k,c,n≤109).

For each question, output a single integer representing the number of pairs $(a,b)$ satisfying all restrictions.