INCPOWK  Increasing Powers of K
Let's define S_{k} as the increasing sequence a_{1}, a_{2}, a_{3}, ... consisting of all those positive integers which are powers of K or sums of distinct powers of K.
For example S_{3} = {1,3,4,9,10,12,13,27,28,30,...}
Your task is given N and K find the N^{th} term of the sequence S_{k}.
Input
The first line of the input contains a single integer T(1 <= T <= 10^{4}) 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 <= 10^{200}).
Output
For each test case print a single line, the N^{th} term of the sequence S_{k}.
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:
20170708 14:49:59
Big numbers... don't take any modulo.. print the whole answer


udit_003:
20160429 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:
20160112 21:24:07
AC in 5 lines of Python :D 

impossible_1:
20150925 13:46:49
one of the toughest submission. 

ISHANI:
20141227 19:54:42
getting internal error in python

Added by:  Angel Paredes 
Date:  20100302 
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 