INCPOWK - Increasing Powers of K
Let's define Sk as the increasing sequence a1, a2, a3, ... consisting of all those positive integers which are powers of K or sums of distinct powers of K.
For example S3 = {1, 3, 4, 9, 10, 12, 13, 27, 28, 30...}
Your task is given N and K find the Nth term of the sequence Sk.
Input
The first line of the input contains a single integer T(1 <= T <= 104) representing the number of test cases. The next T lines consist of two numbers each one separated by a single space:
K (3 <= K <= 9) and N (1 <= N <= 10200).
Output
For each test case print a single line, the Nth term of the sequence Sk.
Example
Input:
8
3 4
3 100
4 3
5 12
6 7
7 239
8 17
9 500
Output:
9
981
5
150
43
958399
4097
48426822
hide comments
starun8795:
2017-07-08 14:49:59
Big numbers... don't take any modulo.. print the whole answer
|
|
udit_003:
2016-04-29 20:43:14
my code is running fine for some smaller inputs but showing time limit exceeded for very bigger ones...how should i address this issue?? |
|
Parth:
2016-01-12 21:24:07
AC in 5 lines of Python :D |
|
impossible_1:
2015-09-25 13:46:49
one of the toughest submission. |
|
ISHANI:
2014-12-27 19:54:42
getting internal error in python
|
Added by: | Angel Paredes |
Date: | 2010-03-02 |
Time limit: | 4.333s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: JAVA NODEJS PERL6 |
Resource: | American Invitational Mathematics Examination 1986 |