Segment Tree with Pruning

Problem 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.

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.

Sample Input

3

100000 1

100000 50

1000000000000000000 1

Sample Output

199999

4095

1999999999999999999

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（3）