Monk and Fredo
Tag(s):

## Math, Medium

Problem
Editorial
Analytics

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 \le T \le 10^5$
$1 \le a < b \le 10^9$
$0 \le d \le 10^9$

SAMPLE INPUT
4
2 3 7
4 10 6
6 14 0
2 3 6

SAMPLE OUTPUT
1
0
1
2

Explanation

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

CodeMonk (Number Theory Part I)

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Math > Number Theory
• Math > Number Theory
• Math > Number Theory