Annie is the talk of the town, who recently won the prize for being the most beautiful woman of her town. Due to her achievement, she has become Dream girl of the youth.
So, many people in the town are trying to propose her, but She has her own demands and only if the demands are satisfied, she will accept the proposal.
She loves two types of chocolates A and B, and she wants someone to gift her D chocolates during the act of proposing.
You have an infinite supply of boxes of chocolates of type A and B, box of type A contains N chocolates whereas box of type B contains M chocolates.
You can gift her D chocolates by using boxes of both the types.(You cannot use any box partially).
Now, You have to find the number of ways in which you can impress her.
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 N(Number of chocolates in box of type A), M(Number of chocolates in box of type B) and D.
Output Format:
For each test case, print the answer in a separate line.
Constraints:
1≤T≤105
1≤N<M≤109
0≤D≤109
Test case 1:
7 chocolates can only be achieved by using 2 boxes of type A and 1 box of type B.
Test case 2:
No combination of boxes exist to satisfy the value of D.
Test case 3:
5 chocolates can be achieved by using 2 combinations.
1) -> 1 box of type A and 0 box of type B.
2)-> 0 box of type A and 5 boxes of type B.
