题目描述
给定y1,y2,y3。
x1*x2=y1+y2*gcd(x1, x2)+y3*lcm(x1, x2)
求满足上述式子的正整数(x1,x2)的对数。
注意:gcd(a, b)表示a和b的最大公约数,lcm(a, b)表示a和b的最小公倍数。
【数据规模和约定】
对于30%的测试数据:y1,y2,y3 <= 100
对于60%的测试数据:y1,y2,y3 <= 10000
对于100%的测试数据:0 <= y1,y2,y3 <= 10^9。T<=500
【样例说明】
满足要求的(x1,x2)有(2,4),(4,2)。
输入格式
输入含有多组数据,第一行一个正整数T,表示这个测试点内的数据组数。
接下来T行,每行有三个整数y1,y2,y3。
输出格式
共T行,每行一个整数,表示对1000000007取模后的答案。如果有无穷多个解,输出-1。
样例输入
样例输出