Zap
题号:NC51058
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。

输入描述:

第一行包含一个正整数n,表示一共有n组询问。接下来n行,每行表示一个询问,每行三个
正整数,分别为a,b,d。

输出描述:

对于每组询问,输出到输出文件zap.out一个正整数,表示满足条件的整数对数。
示例1

输入

复制
2
4 5 2
6 4 3

输出

复制
3
2