Today is Independence Day, everyone is celebrating in their homes (due to corona). But your one friend who has just started learning Dynamic Programming and is so excited after solving coin change problem doesn't want to stay indoors. So you decided to give him a question to test his knowledge (hoping that he would take full day to solve it and thus won't go out). So you tell him, 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 zero number of times).
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 contains an integer T denoting number of testcases.
Each testcase contains of only one line containing three space separated integers a, b and d .
Output Format:
For each testcase, print the answer in a separate line.
Constraints:
1≤T≤105
1≤a<b≤109
0≤d≤109
Note: You may want to use long long, as overflow can occur anytime.
Author - Shivam Raina
Testcase 1: 7 can only be achieved using 2 two times and 3 one time.
Testcase 2: 6 can’t be achieved by using 4 and 10. So 0 ways are there.