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