I'm praying for owning a transparent heart; as well as eyes with tears more than enough...

— Escape Plan, Brightest Star in the Dark

Iris looked at the stars and a beautiful problem emerged in her mind. She is inviting you to solve it so that a meteor shower is believed to form.

There are $$$n$$$ stars in the sky, arranged in a row. Iris has a telescope, which she uses to look at the stars.

Initially, Iris observes stars in the segment $$$[1, n]$$$, and she has a lucky value of $$$0$$$. Iris wants to look for the star in the middle position for each segment $$$[l, r]$$$ that she observes. So the following recursive procedure is used:

First, she will calculate $$$m = \left\lfloor \frac{l+r}{2} \right\rfloor$$$.
If the length of the segment (i.e. $$$r - l + 1$$$) is even, Iris will divide it into two equally long segments $$$[l, m]$$$ and $$$[m+1, r]$$$ for further observation.
Otherwise, Iris will aim the telescope at star $$$m$$$, and her lucky value will increase by $$$m$$$; subsequently, if $$$l \neq r$$$, Iris will continue to observe two segments $$$[l, m-1]$$$ and $$$[m+1, r]$$$.

Iris is a bit lazy. She defines her laziness by an integer $$$k$$$: as the observation progresses, she will not continue to observe any segment $$$[l, r]$$$ with a length strictly less than $$$k$$$. In this case, please predict her final lucky value.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The description of test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 2\cdot 10^9$$$).

Output

For each test case, output a single integer — the final lucky value.

Note

In the first test case, at the beginning, Iris observes $$$[1, 7]$$$. Since $$$[1, 7]$$$ has an odd length, she aims at star $$$4$$$ and therefore increases her lucky value by $$$4$$$. Then it is split into $$$2$$$ new segments: $$$[1, 3]$$$ and $$$[5, 7]$$$. The segment $$$[1, 3]$$$ again has an odd length, so Iris aims at star $$$2$$$ and increases her lucky value by $$$2$$$. Then it is split into $$$2$$$ new segments: $$$[1, 1]$$$ and $$$[3, 3]$$$, both having a length less than $$$2$$$, so no further observation is conducted. For range $$$[5, 7]$$$, the progress is similar and the lucky value eventually increases by $$$6$$$. Therefore, the final lucky value is $$$4 + 2 + 6 = 12$$$.

In the last test case, Iris finally observes all the stars and the final lucky value is $$$1 + 2 + \cdots + 8\,765\,432 = 38\,416\,403\,456\,028$$$.

Bewitching Stargazer

Examples