Background

We are the champions of the Eurocup! Well... almost. Actually, we lost in first round and didn't win any match. But we were beaten by the real champions so, optimistically, we could be the second! Cup competitions are always unfair...

The Problem

Let's consider a cup competition, that consists of N rounds where 2^N teams take part. The winners of each round proceed to the next round. So in round 1 there are 2^N teams, in round 2 there are 2^N-1 teams, and so on. Teams are numbered 0, 1, 2, ..., 2^N -1. The matches in each round are scheduled according to this order. Assume that, when two teams play, the one with the lowest number always wins. In conclusion, in round 1 the matches are: (0 vs. 1), (2 vs. 3), (4 vs.5), ...; in round 2: (0 vs. 2), (4 vs. 6), ... The situation for N=3 is shown in the picture below.

A team, X, is better than all the teams it has beaten, and it is worse than all the teams it has lost with. Moreover, we can apply a sort of transitivity: X is better than all the team that are worse than the teams that are worse than X; and X is worse than the teams that are better than the teams that are better than X. For example, in the case of N=3, team 7 is worse than 6, 4 and 0.

When the competition is finished, all teams are given a ranking from 1 to 2^N (different for each team, 1 for the winner, 2 for the subchampion, etc.). The ranking of team X is R(X). A valid ranking has the following property: if X is better than Y, then R(X) < R(Y). Obviously, there are many possible valid rankings (because there are pairs of teams that we have no information between them). We define the optimistic classification of a team X as the smallest value of R(X) for any valid ranking R. Similarly, the pessimistic classification of X is the biggest value of R(X) for any valid ranking R.

Given the number of rounds, N, and the number of a team, X, you have to compute the optimistic and pessimistic classification of X.

The Input

The first line of the input contains an integer M, indicating the number of test cases. Each test case consists of two integers N and X. N is the total number of rounds in the competition (0<N<31), and X is the number of a team (0<= X <= 2^N -1).

The Output

For each test case, the output should consist of a single line with two integers: the optimistic and the pessimistic classification of the corresponding team.

Sample Input

4
3 1
4 10
2 2
4 15

Sample Output

2 8
3 15
2 3
5 16

如果你把它們全部都轉成二進制的話, 你會發現, 比賽由低位的 bit 開始比較
1 的個數+1 為最佳名次
lowbit 的值也就是他撐到哪一個回合時贏了多少隊

#include <stdio.h>

int main() {
    int t, n, m;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        int tot = 1<<n;
        int tmp = m, cnt = 0;
        while(tmp)
            cnt += tmp&1, tmp >>= 1;
        tmp = (m == 0) ? (1<<n) : (m&-m);
        printf("%d %d\n", cnt+1, tot-tmp+1);
    }
    return 0;
}