/*
Time limit: 5000ms
Memory limit: 256mb

---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/

#include <stdio.h>
#include <stdlib.h>


/**
 * @brief Function to calculate the sum of lucky numbers
 *       in the range [1, n] with at most k digits
 * @param n the upper bound of the range
 * @param k maximum number of digits
 * @return the lucky value in the range [1, n]
 * @note you need use `long long` instead of `int` to store the result 
 *       to avoid overflow
 */
long long solve(int n, int k) {
    // WRITE YOUR CODE HERE

}

// DO NOT MODIFY THE CODE BELOW
int main(void) {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);
        printf("%lld\n", solve(n, k));
    }

    return 0;
}


---------------------------------------End of Code---------------------------------------

## Counting Trains

There are $n$ train cars connected in a row, numbered from $1$ to $n$. Iris, who loves trains, wants to calculate her lucky value for this train.

Initially, Iris examines the entire train segment $[1, n]$, starting with a lucky value of $0$. For each segment $[l, r]$ she examines, Iris follows these rules:
- She finds the middle car position $m = \lfloor (l + r) / 2 \rfloor$
- If the segment length $(r - l + 1)$ is even, she splits it into two equal segments $[l, m]$ and $[m + 1, r]$ for further examination
- If the segment length is odd, she adds $m$ to her lucky value and, if $l \neq r$, continues examining the segments $[l, m - 1]$ and $[m + 1, r]$

Iris has a minimum segment parameter $k$ and will not examine any segment $[l, r]$ with fewer than $k$ cars.

Calculate Iris's final lucky value for the train.

### Input
Multiple test cases. The first line contains an integer $t\, (1\leq t\leq 10)$ — the number of test cases.

Each test case consists of a line with two integers $n$ and $k$ $(1\leq k\leq n \leq 10^7)$.

### 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
```

**Explanation**

For the first case ($n=7$, $k=2$):
- Initial segment $[1,7]$: middle $m=4$, adds 4 to lucky value. Examines $[1,3]$ and $[5,7]$.
- Segment $[1,3]$: middle $m=2$, adds 2. Segments $[1,1]$ and $[3,3]$ are too small.
- Segment $[5,7]$: middle $m=6$, adds 6. Segments $[5,5]$ and $[7,7]$ are too small.
- Final lucky value: $4 + 2 + 6 = 12$.