Fredo and you are talking about a movie that you have recently watched while Monk is busy teaching Number Theory. Sadly, Monk caught Fredo talking to you and asked him to answer his question in order to save himself from punishment. The question says:
Given two weights of a and b units, in how many different ways you can achieve a weight of d units using only the given weights? Any of the given weights can be used any number of times (including 0 number of times).
Since Fredo is not able to answer the question, he asked you to help him otherwise he will get punished.
Note: Two ways are considered different if either the number of times a is used or number of times b is used is different in the two ways.
Input Format:
The first line of input consists of an integer T denoting the number of test cases.
Each test case consists of only one line containing three space separated integers a, b and d.
Output Format:
For each test case, print the answer in a separate line.
Constraints:
1≤T≤105
1≤a<b≤109
0≤d≤109
Test case 1:
7 can only be achived by using 2 two times and 3 one time.
Test case 2:
6 can't be achieved by using 4 and 10. So, 0 ways are there.
Test case 3:
0 can be achieved by using 0 times 6 and 0 times 14. So, there is only one way,
Test case 4:
6 can be achieved by using 2 three times or 3 two times. So, there are two different ways of getting 6.
