Given the value of n, find the k^th number in the sequence produced by the code below.

    void fun(int n)
    {
        if(n>0)
        {
            fun(n-1);
            printf("%d ",n);
            fun(n-1);
        }
    }

Input

First line contains T (number of test-cases, 1 ≤ T ≤ 10⁵)

Next T lines contains two space separated integers n (1 ≤ n ≤ 10¹⁸) and k (1 ≤ k ≤ 10¹⁸)

Output

For each test-case, print an integer representing the k^th number in sequence if it exists otherwise print 0

Example

Input:
5
2 1
2 10
5 4
5 1
5 2

Output:
1
0
3
1
2