Description

Chenjb is struggling with data stucture now. He is trying to solve a problem using segment tree. Chenjb is a freshman in programming contest, and he wrote down the following C/C++ code and ran ''$\texttt{Node* root = build(1, n)}$'' to build a standard segment tree on range $[1,n]$:

Node* build(long long l, long long r) {
    Node* x = new(Node);
    if (l == r) return x;
    long long mid = (l + r) / 2;
    x -> lchild = build(l, mid);
    x -> rchild = build(mid + 1, r);
    return x;
}

Chenjb submitted his code, but unfortunately, got MLE (Memory Limit Exceeded). Soon Chenjb realized that his program will new a large quantity of nodes, and he decided to reduce the number of nodes by pruning:

Node* build(long long l, long long r) {
    Node* x = new(Node);
    if (r - l + 1 <= k) return x;
    long long mid = (l + r) / 2;
    x -> lchild = build(l, mid);
    x -> rchild = build(mid + 1, r);
    return x;
}

You know, Chenjb is a freshman, so he will try different values of $k$ to find the optimal one. You will be given the values of $n$ and $k$, please tell him the number of nodes that will be generated by his new program.

Format

Input

The first line contains a single integer $T$ ($1 \leq T \leq 10\,000$), the number of test cases. For each test case:

The only line contains two integers $n$ and $k$ ($1 \leq k\leq n \leq 10^{18}$), denoting a query.

Output

For each query, print a single line containing an integer, denoting the number of segment tree nodes.

Samples

3
100000 1
100000 50
1000000000000000000 1

199999
4095
1999999999999999999