Paying optimally

All submissions for this problem are available.
The currency of Dholakpur is pretty awesome. There notes have values 1, C, C^{2}, C^{3} ... . The sequence goes on till infinity, so notes have unbounded values.
Little Bheem is a resident of Dholakpur and runs a Laddu shop. He always keeps infinite number of notes of each value with him, but pays using minimum number of notes. For example, if C = 5 and he has to pay 32 rupees, he will pay using one note of value 25, one note of value 5, and two notes of value 1. He cannot pay 32 rupees with fewer than four notes.
Bheem is wondering what is K^{th} smallest amount which, if paid using fewest possible notes, would require exactly S notes.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test is descried by exactly one lines, containing three space separated integers C, S and K.
Output
For each test case, output a separate line containing the required answer.
Constraints
 1 ≤ T ≤ 100
 2 ≤ C ≤ 50
 0 ≤ S ≤ 500
 1 ≤ K ≤ 10^{18}
 The answer will be at most 10^{18}
Subtask 1 (20 points)
K = 1
the answer will be at most 40000000
Time limit is 3 seconds.
Subtask 2 (20 points)
C = 2
the answer will be at most 40000000
Time limit is 3 seconds.
Subtask 3 (20 points)
K is small. Formally, (K1)*(C1) ≤ S
the answer will be at most 40000000
Time limit is 3 seconds.
Subtask 4 (20 points):
the answer will be at most 40000000
Time limit is 3 seconds.
Subtask 5 (20 points):
No special constraints
Time limit is 0.3 seconds.
Sample Input
3
5 1 3
4 3 5
5 4 4
Sample Output
25
18
16
Explanation
For test case# 1, all the amounts which require exactly 1 note are: 1, 5, 25, 125 ...
For test case# 2, all the amounts which require exactly 3 notes are: 3, 6, 9, 12, 18 ...
For test case# 3, all the amounts which require exactly 4 notes are: 4, 8, 12, 16 ...
Author:  utkarsh_lath 
Tester:  
Editorial  http://discuss.codechef.com/problems/COINCHNG 
Tags  binarysearch, greedy, ltime02, medium, utkarsh_lath 
Date Added:  12072013 
Time Limit:  0.3  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 