Cho ba số nguyên dương ~c~, ~d~, ~x~. Bạn cần phải tìm số cặp ~(a,b)~ thỏa mãn ~c*lcm(a,b) - d*gcd(a,b) = x~. Ở đây, ~lcm(a,b)~ là bội chung nhỏ nhất của ~(a,b)~, ~gcd(a,b)~ là ước chung lớn nhất của ~(a,b)~.

Input

• Dòng đầu gồm số nguyên dương ~t~ ~(t \le 10^4)~ là số lượng test case.
• ~t~ dòng sau, mỗi dòng gồm ba số nguyên dương ~c~, ~d~, ~x~ miêu tả test case. ~(1 \le c,d,x \le 10^7)~

Output

• Với mỗi test case, in ra số lượng cặp ~(a,b)~ thỏa mãn.

Sample Test

Input

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

Output

4
3
0
8

Giải thích: Ở test case thứ nhất, có ~4~ cặp thỏa mãn là ~(1,4), (4,1), (3,6), (6,3)~