MOVMRBL - Move Marbles

You have N marbles and K slots. You have to follow the below mentioned rules :

  1. You can put in a marble or take out a marble from slot numbered 1 at any time.
  2. You can put in a marble or take out a marble from slot numbered i only if there exists a marble at the slot i - 1.
  3. The game stops when a marble reaches the slot numbered K for the first time.

Your task is to finish the game in minimum number of valid moves.

Input

The first line contains t, the number of testcases. Then on each line is given two numbers N <= 15, K <= 2^N - 1.

Output

Print two numbers namely the number of "put in" moves and the number of "remove from" moves respectively for all the tests such that you move to the Kth slot in minimum number of valid moves. See explanation section below for more details.

Example

Input: 
1
3 6

Output:
6 3

Explanation

The following are the valid moves for the given input:

  1. PUT IN 1
  2. PUT IN 2
  3. PUT IN 3
  4. REMOVE FROM 2
  5. REMOVE FROM 1
  6. PUT IN 4
  7. PUT IN 5
  8. REMOVE FROM 4
  9. PUT IN 6

Added by:Paranoid Android
Date:2010-03-09
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: OBJC SQLITE
Resource:-

hide comments
2022-02-24 20:15:30 David
@cegprakash Given the constraints of the problem (K <= 2^N - 1), the solution is possible.
2019-05-07 23:45:37 cegprakash
what about impossible cases?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.