Let's define S_k as the increasing sequence a₁, a₂, a₃, ... consisting of all those
positive integers which are powers of K or sums of distinct powers of K.
 
For example S₃ = {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⁴) 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²⁰⁰).

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