H --N and K

Consider a narrowly-sense monotonically increasing sequence of integers greater than or equal to 1 and N, in which no matter which two different numbers are taken from the elements of the sequence, the other does not divide one. Let L be the maximum length of such a sequence, and consider such a sequence (a_1, a_2, ..., a_L). Find the Kth element a_K in this sequence. However, if there are multiple such sequences (a_1 ... a_L), output the minimum possible value for a_K. Also, output -1 when K> L.

Input format

The input consists of multiple inputs. The number of inputs is C set, and the i-th input is N_i, K_i. Test cases are given in the following format.


C
N_1 K_1
...
N_C K_C


Output format

The output consists of C lines. The output on line i is the answer for N_i and K_i.

Constraint

* 1 \ leq C \ leq 10 ^ 5
* 1 \ leq N_i \ leq 10 ^ {18}
* 1 \ leq K_i \ leq N_i
* All input values ​​are integers.



A group of 50 test cases is set to judge this problem. In addition to the above constraints, the test cases included in this group also meet the following constraints.

* C = 1, N_i \ leq 50





Examples

Input

5
3 2
5 2
8 3
10 1
18 12


Output

3
3
5
4
-1


Input

None


Output

None
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;

#define DE 1
#define FI first
#define SE second
#define PB push_back
#define MP make_pair
#define ALL(s) (s).begin(),(s).end()
#define REP(i,n) for (int i = 0; i < (int)(n); ++i)
#define EACH(i,s) for (typeof((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl

template<class T1, class T2> ostream& operator<<(ostream &s, pair<T1,T2> P){return s<<'<'<<P.first<<", "<<P.second<<'>';}
template<class T> ostream& operator<<(ostream &s, vector<T> P) {s<<"{ ";for(int i=0;i<P.size();++i){if(i>0)s<<", ";s<<P[i];}return s<<" }"<<endl;}
template<class T1, class T2> ostream& operator<<(ostream &s, map<T1,T2> P) {s<<"{ ";for(typeof(P.begin()) it=P.begin();it!=P.end();++it){if(it!=P.begin())s<<", ";s<<'<'<<it->first<<"->"<<it->second<<'>';}return s<<" }"<<endl;}





int main() {
    //freopen( "/Users/macuser/Documents/Programming/Contest/input.in", "r", stdin );

    
    int C;
    cin >> C;
    for (int id = 0; id < C; ++id) {
        ll N, K;
        cin >> N >> K;
    
        ll L = (N+1)/2;
        if (K > L) {
            cout << -1 << endl;
            continue;
        }
        if (N == 1 && K == 1) {cout << 1 << endl; continue;}
            
        vector<pair<ll,ll> > seg;
            
        ll temp = N;
        ll fac = 1;
        if (temp % 2 == 0) temp--;
        while (temp != 0) {
            ll p = temp;
            if (p % 2 == 0) --p;
            seg.PB(MP(p,fac));
            temp /= 3;
            fac *= 2;
        }
        reverse(ALL(seg));
        
        //COUT(seg);
        
        ll lo = 0, up = N+1, med;
        while (up-lo > 1) {
            //cout << MP(lo, up) <<", " << med <<  " : " << endl;
            
            med = (up+lo)/2;
            
            ll con = 0;
            for (int i = seg.size()-1; i >= 0; --i) {
                ll temp = 0;
                
                if (med >= seg[i].FI * seg[i].SE) {
                    con += (seg[i].FI+1)/2;
                    break;
                }
                
                ll left;
                if (i != 0) left = seg[i-1].FI + 2;
                else left = 1;
                ll right = seg[i].FI;
                
                ll fac = seg[i].SE;
                ll d = med/fac;
                if (d % 2 == 0) --d;
                
                ll p = max(1LL, left);
                ll q = min(d, right);
                
                temp = (q-p)/2 + 1;
                
                //cout << seg[i] << ": " << MP(right,left) << temp << ", " << con << endl;
                
                if (p <= q) con += temp;
            }
            
            if (con >= K) up = med;
            else lo = med;
        }

        cout << up << endl;
    }
    
    return 0;
}
