Little Chef and the King
All submissions for this problem are available.
Nowadays out little Chef is traveling a lot. While traveling, on one unlucky day, he lost into a mysterious country. Nearby people handed little Chef to the King for investigations. After proper investigation they found little Chef innocent. Little Chef had no money with him to return to his country Byteland, so the King helped him by giving some money.
The monetary system of the country has coins of following values :
K0 , K1 , K2 , K3 , K4 ..... (till infinity)
The King gave him K coins of each type.
The cost of the air ticket from that country to Byteland (his home) is N . What is the minimum number of coins little chef has to spend to buy a ticket ? Little Chef want to spend minimum number of coins so that he can play with the remaining coins in his home !
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The only line of each test case contains two space separated integers N and K as described in the problem statement.
- For each test case, output a single line containing the answer to the corresponding test case.
- 1 ≤ T ≤ 100,000
- 1 ≤ N ≤ 1,000,000,000,000,000,000 (1018)
- 1 ≤ K ≤ 100,000
Input: 2 12 2 18 3 Output: 2 2
|Tags||iitk, mpc, mpc2, simple, triveni|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions