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
Tough task to submit in c/c++/java

Last edit: 2017-07-08 14:58:53
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

Reply (numerix): www.spoj.com/forum/viewtopic.php?f=20&t=22493

Last edit: 2014-12-27 21:40:03

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