All Tracks Basic Programming Recursion Recursion and Backtracking Problem

Converting
Tag(s):

Easy

Problem
Editorial
Analytics

You are given a,b and c.You need to convert a to b.
You can perform following operations :-
1) Multiply a by c.
2) Decrease a by 2.
3) Decrease a by 1.
You can perform this operation in any order and any number of times.
You need to find and print minimum number of steps to convert a to b.

Constraints :-

\(1 \leq t \leq 10^{4}\)

\(0 \leq a,b,c \leq 10^{9}\)

Input : -

First line contains nuber of test cases.

Next \(t\) line for contains three space separated integer  \(a , b , c . \).

Output : -

Print minimum no. of steps as output in new line for each test case.

SAMPLE INPUT
2
3 10 2
11 6 2
SAMPLE OUTPUT
3
3
Explanation

For test case \(1\): -

1) First multple \(3\) with \(2\) then

2) Subtract \(1\) from \(6\) to get \(5\)

3) Multiple \(5\) with \(2\)  to get \(10\).

So, 3 steps.

For test case \(2\): -

1) Subtact \(2\) from \(11\) , 2 times

2) Subtract \(1\) from 7.

So, 3 steps.

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: Bash, 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, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?