Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

C. Bewitching Stargazer
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
I'm praying for owning a transparent heart; as well as eyes with tears more than enough...

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=l+r2.
  • If the length of the segment (i.e. rl+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 lr, Iris will continue to observe two segments [l,m1] 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 (1t105) — the number of test cases. The description of test cases follows.

The only line of each test case contains two integers n and k (1kn2109).

Output

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

Example
Input
6
7 2
11 3
55 13
5801 6
8919 64
8765432 1
Output
12
18
196
1975581
958900
38416403456028
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++8765432=38416403456028.